双栈实现简单表达式求值

双栈实现表达式的求值是使用栈的一个经典例子，它使用一个栈来保存操作符，另外一个栈来保存操作数。
算数表达式由括号、运算符和操作数组成，双栈求值实现过程如下：
1、将操作数压入操作数栈
2、将运算符压入运算符栈
3、忽略左括号
4、在遇到右括号时，弹出一个运算符，再弹出运算符所需的操作数，并将运算符和操作数运算的结果存入操作数栈。
下面为实现一个保留括号（即不省略括号）的简单表达式求值的代码。

代码实现：

import java.util.Scanner;

public class Evaluate {

	MyStack<String> ops = new MyStack<>();//操作符栈
	MyStack<Double> vals = new MyStack<>();//操作数栈

	public double doEvaluate(Scanner sca) {
		while (sca.hasNext()) {
			//扫描输入缓存区
			String s = sca.next();
			if (s.equals("=")) {
				//"="则跳出循环
				break;
			}
			if (s.equals("(")) {
				//如果是左括号，什么也不干
			}else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
				System.out.println("操作符" + s + "入栈了");
				ops.push(s);
			}else if (s.equals(")")) {
				String op = ops.pop();
				double v = vals.pop();
				if (op.equals("+")) {
					v = vals.pop() + v;
				}else if (op.equals("-")) {
					v = vals.pop() - v;
				}else if (op.equals("*")) {
					v = vals.pop() * v;
				}else if (op.equals("/")) {
					v = vals.pop() / v;
				}
				vals.push(v);
				System.out.println("运算结果" + v + "入栈了");
			}else {
				vals.push(Double.parseDouble(s));
				System.out.println("操作数" + Double.parseDouble(s) + "入栈了");
			}
		}
		return vals.pop();
	}
}

测试：

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Evaluate eva = new Evaluate();
		
		System.out.println("请输入一个算术表达式，字符之间请以空格隔开，例如： （ 1.2 + 2.3 ） = ");
		Scanner s = new Scanner(System.in);
		double result = eva.doEvaluate(s);
		System.out.println("最终运算结果是：" + result);
	}
}

运算结果：