算法应用：使用栈实现中缀表达式转后缀表达式

一、基本概念

在继续之前，我们先明确两种表达式的定义：

  • 中缀表达式 (Infix Expression)
    这是我们日常使用的标准算术表达式，操作符位于两个操作数的中间。
    例如：3 + 4 或 (a + b) * c

  • 后缀表达式 (Postfix Expression / Reverse Polish Notation)
    也称为逆波兰表达式，操作符位于两个操作数的后面。后缀表达式在计算时不需要括号，并且计算逻辑非常简单，易于计算机处理。
    例如：3 4 + 或 a b + c *

转换的目标： 将人类易于阅读的中缀表达式，转换为计算机易于处理的后缀表达式。

二、转换算法思想

转换过程的核心是使用一个栈来临时存放操作符。我们从左到右遍历中缀表达式的每一个字符（或token），根据字符类型执行不同的操作。

  • 需要一个栈 s：用于存放操作符。
  • 需要一个结果列表 postfix（或字符串）：用于存储最终的后缀表达式。

转换规则

从左到右扫描中缀表达式，对于每个元素执行以下步骤：

  1. 遇到操作数（数字）：

    • 直接将其追加到 postfix 结果列表中。

  2. 遇到左括号 (：

    • 直接将其压入操作符栈 s 中。

  3. 遇到右括号 )：

    • 持续地从栈 s 中弹出操作符并追加到 postfix 中，直到遇到左括号 ( 为止。
    • 弹出左括号 ( 并丢弃它（括号在后缀表达式中是不需要的）。

  4. 遇到操作符（如 +, -, *, /）：

    • 设当前操作符为 op。
    • 查看栈顶的操作符 top_op。
    • 只要栈 s 不为空、栈顶不是左括号 (、并且 top_op 的优先级大于或等于 op 的优先级，就持续从栈 s 中弹出 top_op 并追加到 postfix 中。
    • 循环结束后，将当前操作符 op 压入栈 s 中。

  5. 遍历完成：

    • 遍历完整个中缀表达式后，检查栈 s 是否还存在操作符。
    • 如果有，将栈中所有剩余的操作符依次弹出并追加到 postfix 中。

关键点：操作符优先级

为了正确处理第4条规则，我们需要为操作符定义优先级。通常的优先级如下：

  • *, / 的优先级高于 +, -。
  • 相同优先级的操作符，例如 + 和 -，遵循从左到右的结合性，因此在规则4中要用“大于或等于”。
操作符 优先级
*, / 2
+, - 1
( 0

三、示例演练

我们通过一个具体的例子 (3 + 4) * 5 - 6 / 2 来手动模拟整个转换过程。

当前Token 操作 操作符栈 s (从底到顶) 后缀表达式 postfix 备注
( 规则2：左括号入栈 (
3 规则1：数字直接输出 ( 3
+ 规则4：+ 入栈 (, + 3 栈顶是 (，优先级最低，直接入栈
4 规则1：数字直接输出 (, + 3, 4
) 规则3：弹出直到 ( 3, 4, + 弹出 + 并输出，然后弹出并丢弃 (
* 规则4：* 入栈 * 3, 4, + 栈为空，直接入栈
5 规则1：数字直接输出 * 3, 4, +, 5
- 规则4：处理 - - 3, 4, +, 5, * - 优先级低于栈顶 *，弹出 * 输出，再压入 -
6 规则1：数字直接输出 - 3, 4, +, 5, *, 6
/ 规则4：处理 / -, / 3, 4, +, 5, *, 6 / 优先级高于栈顶 -，直接入栈
2 规则1：数字直接输出 -, / 3, 4, +, 5, *, 6, 2
(结束) 规则5：清空栈 3, 4, +, 5, *, 6, 2, /, - 依次弹出 / 和 - 并输出

最终，中缀表达式 (3 + 4) * 5 - 6 / 2 转换为了后缀表达式 3 4 + 5 * 6 2 / -。

四、代码实现 (C++)

以下是一个简化的C++实现，假设输入的中缀表达式已经被分割成了一个token列表（例如，数字和操作符之间有空格）。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <unordered_map>

// 获取操作符的优先级
int get_precedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    }
    if (op == '*' || op == '/') {
        return 2;
    }
    return 0; // 其他情况（如括号）
}

// 将中缀表达式字符串转换为后缀表达式字符串
std::string infix_to_postfix(const std::string& infix) {
    std::stack<char> s;
    std::stringstream postfix;
    std::stringstream input(infix);
    std::string token;

    while (input >> token) {
        if (isdigit(token[0])) { // 如果是数字
            postfix << token << " ";
        } else if (token == "(") { // 如果是左括号
            s.push('(');
        } else if (token == ")") { // 如果是右括号
            while (!s.empty() && s.top() != '(') {
                postfix << s.top() << " ";
                s.pop();
            }
            s.pop(); // 弹出左括号
        } else { // 如果是操作符
            while (!s.empty() && s.top() != '(' && get_precedence(s.top()) >= get_precedence(token[0])) {
                postfix << s.top() << " ";
                s.pop();
            }
            s.push(token[0]);
        }
    }

    // 弹出栈中所有剩余的操作符
    while (!s.empty()) {
        postfix << s.top() << " ";
        s.pop();
    }
    
    std::string result = postfix.str();
    // 移除末尾多余的空格
    if (!result.empty()) {
        result.pop_back();
    }

    return result;
}

int main() {
    // 注意：为了简化解析，数字和操作符之间用空格隔开
    std::string infix_expr = "( 3 + 4 ) * 5 - 6 / 2";
    std::string postfix_expr = infix_to_postfix(infix_expr);

    std::cout << "Infix Expression: " << infix_expr << std::endl;
    std::cout << "Postfix Expression: " << postfix_expr << std::endl;
    // 期望输出: 3 4 + 5 * 6 2 / -

    return 0;
}