Dijkstra的双栈算术表达式求值算法 Java实现

背景

《算法 第四版》中讲栈的时候提到了一个算法，用来完成初级算术运算符的操作，自己用Java实现了一下这个算法。

原理

为了方便的实现算法，略去其他的细节，假设表达式是由括号、运算符和操作数（数字）组成。根据以下四种情况从左到右逐个将这些实体送入栈处理：

* 将操作数压入操作数栈；
* 将运算符压入运算符栈；
* 忽略左括号；
* 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。

图解

下图为Dijkstra的双栈算术表表达式求值算法的轨迹。

java实现

这段代码将一个字符串输入后得到计算结果，使用了泛型。简单起见，没有设置其他限制条件，也不允许输入空格。

import java.util.Scanner;
import java.util.Stack;

public class MyEvaluate {
	public static void main(String[] args) {
		Stack<Character> ops = new Stack<Character>();
		Stack<Double> vals = new Stack<Double>();
		
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入一个表达式：");
		String s = sc.nextLine();
		char[] ch = s.toCharArray();
		sc.close();
		
		for(int i = 0; i < ch.length; i++) {
			if(ch[i] == '+') {
				ops.push(ch[i]);
			} else if(ch[i] == '-') {
				ops.push(ch[i]);
			} else if(ch[i] == '*') {
				ops.push(ch[i]);
			} else if(ch[i] == '/') {
				ops.push(ch[i]);
			} else if(ch[i] == '(') {
				//do nothing
			} else if(ch[i] == ')') {	//如果字符为")"，弹出运算符和操作数，计算结果并压入栈
				char op = ops.pop();
				Double val = vals.pop();
				
				if(op == '+') {
					val = vals.pop() + val;
				} else if(op == '-') {
					val = vals.pop() - val;
				} else if(op == '*') {
					val = vals.pop() * val;
				} else if(op == '/') {
					val = vals.pop() / val;
				}
				
				vals.push(val);
			} else {	//将除了运算符和括号的字符，作为double值压入栈
				vals.push(Double.parseDouble(Character.toString(ch[i])));
			}
		}
		
		System.out.println("结果是：" + vals.pop());
	}
}