栈(2)---栈的应用

栈的应用google、百度一大把，这里就弄一个简单的例子：中缀表达式 转 后缀表达式

在中缀表达式（就是我们人类通常写的算术表达式）中，计算需要注意优先级、括号这些问题，和运算符的实际运算次序往往同它们在表达式中的先后次序不一致，所以波兰科学家提出了后缀表达式，把运算符放在两个运算对象的后面。

　　在后缀表达式中看，不存在括号，也不存在运算符优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需扫描一遍便可完成。

中缀表达式转换成后缀表达式：

　　中缀算术表达式转换成对应的后缀算术表达式的规则是：把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。

　　为了转换正确，必须设定一个运算符栈，并在栈底放入一个特殊算符，假定为@，让它具有最低的运算符优先级，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式之后，再令其出栈并写入到后缀表达式中。

　　转换过程如下：从头到尾扫描中缀表达式，若遇到数字则直接写入后缀表达式，若遇到运算符，则比较栈顶元素和该运算符的优先级，当该运算符的优先级大于栈顶元素的时候，表明该运算符的后一个运算对象还没有进入后缀表达式，应该把该运算符暂存于运算符栈中，然后把它的后一个运算对象写入到后缀表达式中，再令其出栈并写入后缀表达式中；若遇到的运算符优先级小于等于栈顶元素的优先级，表明栈顶运算符的两个运算对象已经被写入后缀表达式，应将栈顶元素出栈并写入后缀表达式，对于新的栈顶元素仍进行比较和处理，直到栈顶元素的优先级小于当前等待处理的运算符的优先级为止，然后令该运算符进栈即可。

　　按照上述过程扫描到中缀表达式的末尾，把剩余的运算符依次出栈并写入后缀表达式即可。

　　（对于左括号直接进栈，右括号则使左右两个括号内的运算符都出栈）。

 

看代码比较省力，如下:

package com.matt.stack;

import java.util.*;

public class Expression {

	
	String expression = "";
	

	public Expression() {

	}

	public Expression(String _expression) {
		this.expression = _expression;
	}

	public List<String> toRight() {
		if(this.expression.equals("")||this.expression == null) throw new NullPointerException();
		Stack<String> temp = new Stack<String>();
		List<String> list = new ArrayList<String>();
		char[] charArray = this.expression.toCharArray();
		for (int i = 0; i < charArray.length; i++) {
			switch (charArray[i]) {
			case '+':
				while(!temp.isEmpty()&&!temp.peek().equals("(")){
					list.add(temp.pop());
				}
			    temp.push(String.valueOf(charArray[i]));
				break;
			case '-':
				while(!temp.isEmpty()&&!temp.peek().equals("(")){
					list.add(temp.pop());	
				}
			    temp.push(String.valueOf(charArray[i]));
				break;
			case '*':
				while(!temp.isEmpty()&&(temp.peek().equals("*")||temp.peek().equals("/"))){
					list.add(temp.pop());	
				}
				temp.push(String.valueOf(charArray[i]));
				break;
			case '/':
				while(!temp.isEmpty()&&(temp.peek().equals("*")||temp.peek().equals("/"))){
					list.add(temp.pop());	
				}
				temp.push(String.valueOf(charArray[i]));
				break;
			case '(':
				temp.push(String.valueOf(charArray[i]));
				break;
			case ')':
				do{
					list.add(temp.pop());
				}while(!temp.peek().equals("("));
				temp.pop();
				break;
				
			default:
				list.add(String.valueOf(charArray[i]));
				break;

			}
		}
		while(!temp.isEmpty())
			list.add(temp.pop());
		return list;
	}

	public List<String> toRight(String _expression) {
		this.expression = _expression;
		return toRight();
	}

	private String listtoString(List<String> lst){
		String toStr = "";
		for(String str : lst){
			toStr += str;
		}
		return toStr;
	}
	
	
	public static void main(String[] args) {
		Expression ex = new Expression("a+b*c-(d*e+f)/g");
		
		List<String> lst = ex.toRight();
		System.out.println(ex.listtoString(lst));
		
		lst = ex.toRight("1+2-5*(5-4)*6-(6-1)");
		System.out.println(ex.listtoString(lst));
		
		lst = ex.toRight("1*2/(2+1)*7");
		System.out.println(ex.listtoString(lst));
		
	}

}