表达式求值：Java

import java.util.ArrayList;
import java.util.Stack;


public class PostfixExp {

	private Stack<String> opStack;
	private Stack<String> expStack;
	private String[] ops = {"+", "-", "*", "/", "(", ")", "#"};
	
	public PostfixExp() {
		opStack = new Stack<String>();
		expStack = new Stack<String>();
	}
	
	private boolean isOp(char c) {
		String cStr = Character.toString(c);
		
		for (String op : ops) {
			if(cStr.equals(op)) {
				return true;
			}
		}
		
		return false;
	}
	
	private boolean isOp(String str) {
		for(String op : ops) {
			if(str.equals(op)) {
				return true;
			}
		}
		
		return false;
	}
	
	private int getOpPriority(String op){
		if("+".equals(op) || "-".equals(op)) {
			return 1;
		}
		else if("*".equals(op) || "/".equals(op)) {
			return 2;
		}
		else if("(".equals(op)) {
			return 3;
		}
		else if("#".equals(op)) {
			return 0;
		}
		
		return Integer.MAX_VALUE;
	}
	
	public String[] getItems(String str) {
		ArrayList<String> list = new ArrayList<String>();
		
		// Remove all blank spaces.
		str = str.replaceAll("\\s", "");
		
		int i = 0;
		StringBuilder sBuilder = new StringBuilder();
		while(i < str.length()) {
			if(i == str.length() - 1) {
				sBuilder.append(
						Character.toString(str.charAt(i)));
				list.add(sBuilder.toString());
			}
			
			if(!isOp(str.charAt(i))) {
				sBuilder.append(
					Character.toString(str.charAt(i)));
				
			}
			else {
				if(sBuilder.length() > 0) {
					list.add(sBuilder.toString());
					sBuilder.delete(0, sBuilder.length());
				}
				list.add(Character.toString(str.charAt(i)));
			}
			
			++i;
		}

		list.add("#");

		String[] result = new String[list.size()];
		return list.toArray(result);
	}
	
	public ArrayList<String> change2PostfixExp(String normalExp) {
		ArrayList<String> expList = new ArrayList<String>(); 
		String[] items = getItems(normalExp);
		
		opStack.clear();
		expStack.clear();
		
		opStack.push("#");
		
		int i = 0;
		while(i < items.length) {
			//System.out.println(i + ":" + items[i]);
			if(!isOp(items[i])) {
				expList.add(items[i]);
			}
			else {
				if(items[i].equals(")")){
					while(!opStack.isEmpty() && !opStack.peek().equals("(")) {
						expList.add(opStack.pop());
					}
					
					if(!opStack.isEmpty() && opStack.peek().equals("(")) {
						opStack.pop();
					}
					++i;
					continue;
				}
				
				if(items[i].equals("#")) {
					while(!opStack.isEmpty() && !opStack.peek().equals("#")) {
						expList.add(opStack.pop());
					}
					break;
				}
				
				if(!opStack.isEmpty()) {
					while(!opStack.isEmpty() 
							&& (getOpPriority(opStack.peek()) >= getOpPriority(items[i])
							&& !opStack.peek().equals("("))
					) {
						expList.add(opStack.pop());
					}
					opStack.push(items[i]);
				}
			}
			
			++i;
		}
		
		return expList;
	}
	
	public double calculate(ArrayList<String> postfixExp) {
		Stack<Double> calcStack = new Stack<Double>();
		
		int i = 0;
		String ite = null;
		double result = Double.MAX_VALUE;
		
		while(i < postfixExp.size()) {
			ite = postfixExp.get(i);
			if(!isOp(postfixExp.get(i))) {
				calcStack.push(new Double(
								Double.parseDouble(
										postfixExp.get(i))
				));
			}
			else {
				double num2 = calcStack.peek();
				calcStack.pop();
				if(!calcStack.isEmpty()) {
					double num1 = calcStack.peek();
					calcStack.pop();
					
					if("*".equals(ite)) {
						result = num1 * num2;
					}
					else if("+".equals(ite)) {
						result = num1 + num2;
					} 
					else if("-".equals(ite)) {
						result = num1 - num2;
					} 
					else if("/".equals(ite)) {
						result = num1 / num2;
					} 
					System.out.println(num1 + "\t" + ite + "\t" + num2 + " = " + result);
					calcStack.push(result);
				}
			}
			++i;
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		PostfixExp pExp = new PostfixExp();
		
		//String exp = "a + b*c + (d * e + f) * g";
		//string exp = "1+1+3*2*3-4";
		//string exp = "2+(1+3)*2*3-4";
		//string exp = "2+1+3*2*(3-4)";
		String exp = "(13+10/2)*21*(39-4)";
		String case1 = "(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))";
		String case2 = "(6*7+9+8/2*12+12/3)+88/11";
		String case3 = "(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))";
		String case4 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
		String case5 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
		String case6 = "(3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";

		ArrayList<String> expList = pExp.change2PostfixExp(case6);
		for(String item : expList) {
			System.out.print(item + " ");
		}
		System.out.println("\n");
		System.out.println("My answer is \t\t" + pExp.calculate(expList));
		
		int rightAnswer = (3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))));
		System.out.println("The right answer is \t" + rightAnswer);
		
		System.out.println();
	}

}