《算法4第一章》笔记（七）双栈算术表达式求值算法

说明：

• 输入只能为左括号，右括号，运算符和数字。
• 不考虑省略括号的算术表达式。

该方法由E.W.Dijkstra在20世纪60年代发明。

处理步骤如下：

1. 将操作数压入操作数栈。
2. 将运算符压入运算符栈。
3. 忽略左括号。
4. 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作栈中。
5. 在处理完最后一个右括号后，操作数栈上只会有一个值，它就是表达式的值。

源码：

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

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        while(!StdIn.isEmpty()) {
                // 读取字符，如果是运算符则压入栈
            String s = StdIn.readString();
            if ("(".equals(s)) {
                // 忽略左括号，其他运算符压入运算符栈
            } else if ("+".equals(s)) {
                ops.push(s);
            } else if ("-".equals(s)) {
                ops.push(s);
            } else if ("*".equals(s)) {
                ops.push(s);
            } else if ("/".equals(s)) {
                ops.push(s);
            } else if ("sqrt".equals(s)) {
                ops.push(s);
            } else if (")".equals(s)) {
                    // 如果字符为")"，弹出运算符和操作数，计算结果并压入栈
                String op = ops.pop();
                double v = vals.pop();
                if ("+".equals(op)) {
                    v = vals.pop() + v;
                } else if ("-".equals(op)) {
                    v = vals.pop() - v;
                } else if ("*".equals(op)) {
                    v = vals.pop() * v;
                } else if ("/".equals(op)) {
                    v = vals.pop() / v;
                } else if ("sqrt".equals(op)) {
                    v = Math.sqrt(v);
                }
                vals.push(v);
            } else {
                    // 操作数压入操作数栈
                vals.push(Double.parseDouble(s));
            }
        }
        StdOut.println(vals.pop());
    }
}