Dijkstra双栈表达式求值算法

以表达式"(1+((2+3)*(4*5)))"为例：

算法分四个步骤：

1. 将操作数压入操作数栈
2. 将运算符压入运算符栈
3. 忽略左括号
4. 在遇到右括号时，弹出一个运算符并弹出所需数量的操作数，运算结果并将结果压入操作数栈

处理完最后一个右括号后，操作数栈中只剩下一个数，就是表达式的值。

public class expression {public static void main(String[] args) {Stack<Character> ops = new Stack<Character>();//运算符栈Stack<Integer> vals = new Stack<Integer>();//操作数栈String str = "(1+((2+3)*(4*5)))";for(int i=0;i<str.length();i++) {char ch = str.charAt(i);if(ch == '(');//忽略左括号else if(ch == '+' || ch == '-' || ch == '*' || ch =='/') ops.push(ch);//操作数压入操作数栈else if(ch == ')') {char op = ops.pop();int v = vals.pop();if(op == '+')	v = vals.pop() + v;if(op == '-')	v = vals.pop() - v;if(op == '*')	v = vals.pop() * v;if(op == '/')	v = vals.pop() / v;vals.push(v);}else vals.push(Integer.parseInt(String.valueOf(ch)));//运算符压入运算符栈}System.out.println(vals.pop());}
}