表达式解析的实现

2020-01-27 20:13

#algorithm

#eval-exp

#infix

#postfix

背景

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

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

代码解释

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

递归实现

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

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

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

堆栈实现

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void visit() {   // infix
  visit(left)
  visit(current) // visit in middle
  visit(right)
}

void visit() {   // prefix
  visit(current) // visit first
  visit(left)
  visit(right)
}

void visit() {   // postfix
  visit(left)
  visit(right)
  visit(current) // visit last
}

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


static int precedence(char op)
{
    switch (op) {
    default: assert(false);
    case '(':
    case '#': return 1;
    case '+':
    case '-': return 2;
    case '*':
    case '/': return 3;
    }
}

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


for (const char* p = infix_.c_str(); *p; ++p) {
    if (*p >= '0' && *p <= '9') {
        postfix_ += *p;
    } else if (*p == '(') {
        stack.push_back(*p);
    } else if (*p == ')') {
        while (stack.back() != '(') {
            postfix_ += stack.back(); stack.pop_back();
        }
        stack.pop_back();
    } else {
        while (precedence(*p) <= precedence(stack.back())) {
            postfix_ += stack.back(); stack.pop_back();
        }
        stack.push_back(*p);
    }
}
while (stack.back() != '#') {
    postfix_ += stack.back(); stack.pop_back();
}