算法4学习-1.3.1.7 Dijkstra双栈算术表达式求值法

决定今晚开始看算法4。虽然正值考试期间,但是总要有个开始不是么?

书上基础部分的例子,很不错的思路，改动的地方是把原书中的if嵌套改成了switch。

运行结果

代码

import java.util.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
* Created by tuzhis on 2016年1月11日.
*/
public class Evaluate {
    public static void main(String[] args){
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        StdOut.println("% java Evaluate");
        while (!StdIn.isEmpty()){
            //读取字符,如果是运算符则压入栈
            String s = StdIn.readString();
            switch (s) {
                case "(":
                    break;
                case "+":
                case "-":
                case "*":
                case "/":
                case "sqrt":
                    ops.push(s);
                    break;
                case ")":
                    String  op = ops.pop();
                    double v = vals.pop();
                    switch (op) {
                        case "+":
                            v = vals.pop() + v;
                            break;
                        case "-":
                            v = vals.pop() - v;
                            break;
                        case "*":
                            v = vals.pop() * v;
                            break;
                        case "/":
                            v = vals.pop() / v;
                            break;
                        case "sqrt":
                            v = Math.sqrt(v);
                            break;
                        default:
                            break;
                    }
                    vals.push(v);
                    break;
                //如果字符既非运算符也不是括号，将它作为double值压入栈
                default:
                    vals.push(Double.parseDouble(s));
                    break;
            }
            
        }
        StdOut.println(vals.pop());
    }

}