前中后缀表达式

一、 日常生活中的数学表达式

我们熟悉的“中缀表达式”

在日常学习中，我们最常写的数学算式是这个样子的：

$$(3 + 4) \times 5 - 6$$

这种把运算符（比如 $+$, $-$, $\times$, $\div$）放在两个数字中间的写法，我们称之为 中缀表达式 (Infix Notation)。它非常直观，符合我们的阅读习惯。对于简单的计算，中缀表达式清晰明了。

运算符的优先级与括号

然而，中缀表达式有一个“麻烦”之处：运算顺序。

例如，对于 $3 + 4 \times 5$，我们会先算 $4 \times 5$，再算 $3 + 20$。这是因为我们规定了 $\times$ 的 优先级 高于 $+$。

如果想先算 $3+4$ 怎么办？我们就需要使用 括号 来改变运算顺序，写作 $(3 + 4) \times 5$。

对于人类来说，这套“优先级+括号”的规则我们从小学习，已经习以为常。但对于逻辑严谨的计算机来说，处理这套规则就显得有些复杂。计算机需要反复扫描表达式，判断优先级，处理括号，这大大降低了计算效率。为了解决这个问题，科学家们发明了更适合计算机处理的表达式形式。

二、 计算机的视角：前缀与后缀表达式

为了摆脱括号和优先级的束缚，波兰数学家扬·乌卡谢维奇发明了一种全新的表达式表示方法，这便是 前缀表达式。与之对应的，还有后来被广泛应用的 后缀表达式。

什么是前缀表达式 (波兰表示法)

前缀表达式 (Prefix Notation)，又称为 波兰表示法 (Polish Notation)，它有一个核心特点：将运算符写在操作数的前面。

我们来看几个例子：

中缀表达式	前缀表达式
$3 + 4$	$+ \ 3 \ 4$
$3 - 4$	$- \ 3 \ 4$
$3 \times 4$	$\times \ 3 \ 4$

对于更复杂的表达式 $(3 + 4) \times 5$，可以这样理解：

1. 首先，这是一个乘法运算，其中一个操作数是 $5$，另一个操作数是 $(3+4)$ 这个整体。
2. 所以，我们把 $\times$ 提到最前面，表达式变为：$\times \ (3+4) \ 5$。
3. 接着，我们处理 $(3+4)$，将其转换为前缀表达式 $+ \ 3 \ 4$。
4. 最后，将转换后的结果替换回去，得到：$\times \ + \ 3 \ 4 \ 5$。

我们再看一个例子，$3 + (4 \times 5)$：

1. 这是一个加法，操作数是 $3$ 和 $(4 \times 5)$。
2. 把 $+$ 提前：$+ \ 3 \ (4 \times 5)$。
3. 将 $(4 \times 5)$ 转换为 $\times \ 4 \ 5$。
4. 替换回去得到：$+ \ 3 \ \times \ 4 \ 5$。

什么是后缀表达式 (逆波兰表示法)

后缀表达式 (Postfix Notation)，又称 逆波兰表示法 (Reverse Polish Notation, RPN)，它的规则与前缀表达式正好相反：将运算符写在操作数的后面。

同样看几个例子：

中缀表达式	后缀表达式
$3 + 4$	$3 \ 4 \ +$
$3 - 4$	$3 \ 4 \ -$
$3 \times 4$	$3 \ 4 \ \times$

对于复杂表达式 $(3 + 4) \times 5$：

1. 这是一个乘法，操作数是 $(3+4)$ 和 $5$。
2. 把 $\times$ 放到最后面：$(3+4) \ 5 \ \times$。
3. 将 $(3+4)$ 转换为后缀表达式 $3 \ 4 \ +$。
4. 替换回去，得到：$3 \ 4 \ + \ 5 \ \times$。

对于 $3 + (4 \times 5)$：

1. 这是一个加法，操作数是 $3$ 和 $(4 \times 5)$。
2. 把 $+$ 放到最后面：$3 \ (4 \times 5) \ +$。
3. 将 $(4 \times 5)$ 转换为 $4 \ 5 \ \times$。
4. 替换回去，得到：$3 \ 4 \ 5 \ \times \ +$。

为什么计算机喜欢前缀/后缀表达式？

前缀和后缀表达式最大的优点在于——它们的运算顺序是唯一确定的，完全不需要括号和优先级规则。

• 对于前缀表达式：从右至左扫描，遇到数字则压入一个栈，遇到运算符则从栈中弹出两个数字进行计算，并将结果压回栈中。
• 对于后缀表达式：从左至右扫描，遇到数字则压入一个栈，遇到运算符则从栈中弹出两个数字进行计算，并将结果压回栈中。

由于这种明确的、线性的处理方式，计算机执行起来非常高效，无需进行复杂的语法分析。这使得它们在编译器的设计和算法实现中扮演着至关重要的角色。

三、 表达式之间的转换

将我们习惯的中缀表达式，转换为计算机擅长的后缀或前缀表达式，是算法中的一个经典问题。这里我们主要介绍应用最广的“中缀转后缀”。

中缀转后缀（调度场算法 Shunting-yard Algorithm）

这个算法由计算机科学家艾兹格·迪杰斯特拉（Edsger Dijkstra）提出，因其过程很像火车在调度场中编组调度的过程而得名。其核心工具是 一个栈，用来临时存放运算符。

算法思想

我们从左到右扫描中缀表达式：

• 如果遇到 数字，直接输出到结果序列中。
• 如果遇到 左括号 (，它比较特殊，直接压入栈中。它像一个“哨兵”，标志着一个新计算层级的开始。
• 如果遇到 右括号 )，则不断从栈顶弹出运算符并输出，直到遇到左括号 ( 为止。这对括号本身不输出，它们的作用已经完成。
• 如果遇到 运算符（$+, -, \times, \div$），就需要与栈顶的运算符进行比较：
  • 只要栈不为空、栈顶不是左括号 (，并且栈顶运算符的优先级 大于或等于 当前运算符，就持续将栈顶运算符弹出并输出到结果序列。
  • 上述循环结束后，将当前运算符压入栈中。

扫描结束后，将栈中剩余的所有运算符依次弹出并输出。最终得到的结果序列就是后缀表达式。

为了方便，我们定义运算符的优先级：

• $\times, \div$ 的优先级为 2
• $+, -$ 的优先级为 1

实例演示

我们来转换这个经典的中缀表达式：9 + (3 - 1) * 3 + 10 / 2

当前字符	动作	运算符栈 (op)	结果列表 (res)
9	数字，直接输出	(空)	9
+	栈空，+ 入栈	+
(	左括号，入栈	+ (
3	数字，直接输出		9 3
-	栈顶为 (，不比较，- 入栈	+ ( -
1	数字，直接输出		9 3 1
)	弹出直到 (	+	9 3 1 -
*	栈顶 + 优先级低，* 入栈	+ *
3	数字，直接输出		9 3 1 - 3
+	*优先级高，弹出*。+优先级等，弹出+。+入栈	+	9 3 1 - 3 * +
10	数字，直接输出		9 3 1 - 3 * + 10
/	栈顶 + 优先级低，/ 入栈	+ /
2	数字，直接输出		9 3 1 - 3 * + 10 2
(结束)	弹出栈中所有元素	(空)	9 3 1 - 3 * + 10 2 / +

最终的后缀表达式为 9 3 1 - 3 * + 10 2 / +。

该算法的时间和空间复杂度均为 $O(N)$，其中 $N$ 是表达式中元素的数量。因为每个元素（数字或操作符）都只进出一次结果列表和操作符栈。

中缀转前缀

中缀转前缀的方法与转后缀非常相似，但有两个关键区别：

1. 从右到左 扫描中缀表达式。
2. 遇到 右括号 ) 直接入栈，遇到 左括号 ( 则触发弹出操作（与转后缀时括号的行为相反）。
3. 最终得到的结果序列需要 反转 一次，才是最终的前缀表达式。

一个巧妙的实现思路： 在竞赛中，有一种更便捷的实现方法：

1. 将原始中缀表达式 整体反转。
2. 在反转后的串中，将所有的 ( 替换为 )，将 ) 替换为 (。
3. 对这个新串运行一遍 中缀转后缀 的算法。
4. 将得到的后缀表达式 再次反转，即为所求的前缀表达式。

本质上，这相当于在处理一个“镜像”的表达式，利用了后缀与前缀的对称性。

四、 表达式的求值

后缀和前缀表达式的求值过程是栈结构应用的绝佳范例，其逻辑比解析中缀表达式简单得多。

后缀表达式的求值

算法思想

准备一个数字栈。从左到右遍历后缀表达式：

• 如果遇到 数字，则将其压入栈中。
• 如果遇到 运算符（例如 +, -, *, /），则从栈中 连续弹出两个 数字（注意顺序：先弹出的是右操作数，后弹出的是左操作数）。用该运算符对这两个数字进行计算，然后将计算结果 压回栈中。

遍历结束后，栈中唯一剩下的那个数字，就是整个表达式的最终计算结果。

C++ 代码实现与解析

题意概括

给定一个后缀表达式（也称逆波兰表达式），其中只包含非负整数和四则运算符（+, -, *, /），求出其值。表达式中的元素由空格分隔。 注意：此处的除法为整数除法，结果向零截断（与 C++ 默认行为一致）。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    // IO优化
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    stack<ll> st; // 用于计算的数字栈
    string s;

    // 逐个读取以空格分隔的字符串
    while (cin >> s) {
        if (s == "+" || s == "-" || s == "*" || s == "/") {
            // 遇到运算符，弹出两个数进行计算
            ll b = st.top(); // 先弹出的是右操作数
            st.pop();
            ll a = st.top(); // 后弹出的是左操作数
            st.pop();

            if (s == "+") st.push(a + b);
            if (s == "-") st.push(a - b);
            if (s == "*") st.push(a * b);
            if (s == "/") st.push(a / b);
        } else {
            // 遇到数字，转换成long long并压入栈
            st.push(stoll(s));
        }
    }

    cout << st.top() << endl; // 最后栈顶元素即为结果

    return 0;
}

代码解释

1. 我们使用 std::stack<ll> 来作为数字栈。
2. 通过 while (cin >> s) 循环，我们可以不断读取被空格隔开的字符串，无论是数字还是运算符。
3. 当读取到的字符串 s 是运算符时，我们从栈 st 中弹出两个元素。根据栈“后进先出”的特性，第一个弹出的 b 是运算中的第二个操作数，第二个弹出的 a 是第一个操作数。计算 a op b 的结果，并将结果压回栈中。
4. 如果 s 是数字，我们使用 stoll (string to long long) 将其转换为数字并压入栈。
5. 当所有输入都被处理完毕后，while 循环结束。此时，栈中应该只剩下一个元素，即最终的计算结果，我们将其输出。

复杂度分析

• 时间复杂度: $O(N)$，其中 $N$ 是后缀表达式中元素（数字和运算符）的数量。我们对每个元素只进行一次入栈或出栈操作。
• 空间复杂度: $O(N)$，在最坏的情况下（例如表达式全是数字），我们需要将所有数字都压入栈中。

前缀表达式的求值

前缀表达式的求值过程与后缀表达式类似，只是遍历方向和弹栈顺序有所不同。

算法思想： 从 右到左 遍历前缀表达式。

• 如果遇到 数字，压入栈中。
• 如果遇到 运算符，从栈中弹出两个数字。关键在于顺序：第一个弹出的数是左操作数，第二个弹出的数是右操作数。用该运算符对这两个数进行计算，然后将结果压回栈中。

遍历结束后，栈顶的唯一元素就是结果。

实例演示

我们来求值一个包含非对称运算的前缀表达式： - \ 10 \ * \ 2 \ 3 (对应中缀 10 - (2 * 3))

1. 从右向左扫描，遇到 3，入栈。栈：[3]
2. 遇到 2，入栈。栈：[3, 2]
3. 遇到 *，弹出 2 (左操作数 a)，再弹出 3 (右操作数 b)。计算 a * b 即 2 * 3 = 6。将 6 入栈。栈：[6]
4. 遇到 10，入栈。栈：[6, 10]
5. 遇到 -，弹出 10 (左操作数 a)，再弹出 6 (右操作数 b)。计算 a - b 即 10 - 6 = 4。将 4 入栈。栈：[4]
6. 扫描结束，栈顶元素 4 即为最终结果。

中缀表达式：符合人类习惯，但需要处理复杂的优先级和括号规则。

前缀/后缀表达式：无歧义，无需括号，运算顺序由位置唯一确定，非常适合用栈进行高效求值，是编译器和解释器青睐的内部表示形式。