背景

赶在春节前，二宝出生，出院后便一直宅在家中各种忙。最近又赶上全国肺炎大规模疫情，在囤积了足够的干粮后，全家人更加几乎到了足不出户的地步。除了帮着给二宝喂养换洗外，我闲来无事时，便开始用零星时间折腾各种算法和小工具实现。

在这个过程中，遇到好几个地方，都涉及表达式解析的问题，即给定一个表达式的字符串，程序需要解析并计算出表达式的结果值。过去，我一直使用递归函数的方式实现，但这种方式扩展起来不够方便。今天，趁着有空，就仔细研究了一下经典的堆栈式实现，并自己尝试写了两个简单的示例代码：

代码解释

这两个代码文件，都展示了对同一个字符串“1*(2+3/4)”的解析，假定字符串中不存在空格，只考虑个位整数，只处理加减乘除四则运算。

递归实现

前一个文件（recursive.cpp），采用的是间接递归函数的实现方式。这种方式很直观，它用函数“硬”编码的方式，表示了如下运算规则定义：

text 
1expression := term { ('+'|'-') term }  # 多个term用'+'或'-'连接
2term := factor { ('*'|'/') factor }    # 多个factor用'*'或'/'连接
3factor := number | '(' expression ')'  # 每个factor，可能是数字，可能是括号包含的expression
共 3 行

写起来代码逻辑很直观，也很简练。但这里仅仅处理了两个级别的运算符（加减法算一级，乘除法算一级），一旦规则复杂，编码就会相应变得更加复杂，每次扩展都需要重新定义函数及其互相调用关系。

堆栈实现

后一个文件（stack.cpp），采用的是算法设计教科书上的经典堆栈方式。借助堆栈，把输入的“中缀表达式（infix）”转换为“后缀表达式（postfix）”，进而可以方便地进行求值运算。

在解释代码逻辑前，先简单解释下基本概念：“中缀表达式”，顾名思义，是把运算符（+、-、*和/）放在被运算的两个数中间。而相应地，“后缀表达式”，则是先写出两个被运算的数字，再把运算符写到后面。此外，还有“前缀表达式（prefix）”，则是先写运算符，然后再写两个数字。以“1*(2+3/4)”为例，其二叉树表示如下：

text 
1    (*)
2   /   \
3  1    (+)
4      /   \
5     2    (/)
6         /   \
7        3     4
共 7 行

相应的三种表达式的写法分别是：

  • 中缀表达式：1 * (2 + 3 / 4)
  • 前缀表达式：* 1 + 2 / 3 4
  • 后缀表达式：1 2 3 4 / + *

这三种表达式，分别对应了三种二叉树遍历方式：

cpp 
 1void visit() {   // infix
 2  visit(left)
 3  visit(current) // visit in middle
 4  visit(right)
 5}
 6
 7void visit() {   // prefix
 8  visit(current) // visit first
 9  visit(left)
10  visit(right)
11}
12
13void visit() {   // postfix
14  visit(left)
15  visit(right)
16  visit(current) // visit last
17}
共 17 行

“前缀表达式”和“后缀表达式”中，都不再有小括号，而以字符排列的顺序，直接表达了运算的先后顺序。

堆栈方法的核心在于，定义出不同运算符的“优先级”：

cpp 
 1static int precedence(char op)
 2{
 3    switch (op) {
 4    default: assert(false);
 5    case '(':
 6    case '#': return 1;
 7    case '+':
 8    case '-': return 2;
 9    case '*':
10    case '/': return 3;
11    }
12}
共 12 行

然后，准备一个堆栈（预置一个“#”号表示结束），逐个读取中缀表达式的每个字符，依如下逻辑进行处理：

  • 遇到操作数，直接追加到结果（后缀表达式）字符串中；
  • 遇到左括号（(），压入堆栈；
  • 遇到右括号（)），从堆栈弹出每个运算符，并追加到结果字符串，直至左括号；
  • 其他情况（都是运算符），则比较该运算符的优先级，低于或等于堆栈顶部的运算符，则将该栈顶运算符弹出，追加到结果字符串中，直至栈顶运算符高于当前运算符，则将当前运算符压入堆栈。

处理完成整个字符串后，将堆栈中的剩余内容，逐个弹出并追加到结果字符串。具体实现代码如下：

cpp 
 1for (const char* p = infix_.c_str(); *p; ++p) {
 2    if (*p >= '0' && *p <= '9') {
 3        postfix_ += *p;
 4    } else if (*p == '(') {
 5        stack.push_back(*p);
 6    } else if (*p == ')') {
 7        while (stack.back() != '(') {
 8            postfix_ += stack.back(); stack.pop_back();
 9        }
10        stack.pop_back();
11    } else {
12        while (precedence(*p) <= precedence(stack.back())) {
13            postfix_ += stack.back(); stack.pop_back();
14        }
15        stack.push_back(*p);
16    }
17}
18while (stack.back() != '#') {
19    postfix_ += stack.back(); stack.pop_back();
20}
共 20 行