看到p79，讲栈的一个应用——算术表达式求值，突然想起来这是来我现在这家公司面试的时候，被问的一道题。当年年少无知写计算器的时候，算术表达式求值用的是正则表达式的匹配（不涉及括号），面试给出的的答案也是这种办法。看到书里用栈来解决，真是牛逼。

DJ双栈算术表达式求值算法描述

这个算法是 E.W.Dijkstra大神发明，使用两个栈，一个用于保存运算符，一个用于保存操作数。（这个算法使用括号）

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

在处理完最后一个右括号之后，操作数栈上只会有一个值，就是表达式的值。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Evaluate {
  public static void main(String[] args) {
    Stack<String> ops = new Stack<String>();
    Stack<Double> vals = new Stack<Double>();
    while (!StdIn.isEmpty()) { 
      // 读取字符,如果是运算符则压入栈
      String s = StdIn.readString();
      if (s.equals("("));
      else if (s.equals("+"))
        ops.push(s);
      else if (s.equals("-"))
        ops.push(s);
      else if (s.equals("*"))
        ops.push(s);
      else if (s.equals("/"))
        ops.push(s);
      else if (s.equals("sqrt"))
        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;
        else if (op.equals("sqrt")) v = Math.sqrt(v);
          vals.push(v);
      } // 如果字符既非运算符也不是括号,将它作为 double 值压入栈
      else vals.push(Double.parseDouble(s));
    }
    StdOut.println(vals.pop());
  }
}

它展示了一种重要的计算模型:将一个字符串解释为一段程序并执行该程序得到结果。

参考

  • 《算法》p79-p80