Dijkstra双栈算术表达式求值算法

  1. import edu.princeton.cs.algs4.StdIn;
  2. import edu.princeton.cs.algs4.StdOut;
  4. public class Evaluate {
  5.     public static void main(String[] args){
  6.         ResizingArrayStack<String> ops = new ResizingArrayStack<>();
  7.         ResizingArrayStack<Double> vals = new ResizingArrayStack<>();
  9.         while (!StdIn.isEmpty()){
  10.             String s = StdIn.readString();
  11.             if(s.equals("("));
  12.             else if(s.equals("+")) ops.push(s);
  13.             else if(s.equals("-")) ops.push(s);
  14.             else if(s.equals("*")) ops.push(s);
  15.             else if(s.equals("/")) ops.push(s);
  16.             else if(s.equals("sqrt")) ops.push(s);
  17.             else if(s.equals(")")){
  18.                 String op = ops.pop();
  19.                 double val = vals.pop();
  20.                 if(op.equals("+")) val += vals.pop();
  21.                 else if(op.equals("-")) val -= vals.pop();
  22.                 else if(op.equals("*")) val *= vals.pop();
  23.                 else if(op.equals("/")) val = vals.pop() / val;
  24.                 else if(op.equals("sqrt")) val = Math.sqrt(val);
  25.                 vals.push(val);
  26.             }
  27.             else {
  28.                 vals.push(Double.parseDouble(s));
  29.             }
  30.         }
  31.         StdOut.println(vals.pop());
  32.     }
  33. }

要点

  1. 准备两个栈:运算符栈,操作数栈
  2. 忽略左括号,将操作数和运算符分别压入对应栈内
  3. 遇到右括号,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的结果压入操作数栈
  4. 方法局限性:最多只能有两个操作数在括号内运算且算式必须有左括号和右括号

注意事项
所有的字符间都要以空格隔开,在控制台下StdIn.isEmpty()需要接收ctrl+z才能结束输入,在idea中同理接收ctrl+d才能结束输入