颜林林的个人网站

Linlin Yan's Personal Website

表达式解析的实现

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 / + *

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

 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();
}