将中缀表达式转换为后缀表达式

在理解中缀表达式转换为后缀表示法之前，我们应该分别了解中缀和后缀表示法。

中缀和后缀都是表达式。表达式由常量、变量和符号组成。符号可以是运算符或括号。所有这些组成部分必须根据一组规则排列，以便可以使用这组规则评估所有这些表达式。

表达式示例

5 + 6

A - B

(P * 5)

以上所有表达式都具有共同的结构，即运算符位于两个操作数之间。操作数是进行操作的对象或值。在上面的表达式中，5、6 是操作数，而'+'、'-'和'*'是运算符。

什么是中缀表示法？

当运算符写在操作数之间时，称为中缀表示法。操作数不一定是常量或变量；它也可以是表达式本身。

例如：

(p + q) * (r + s)

在上面的表达式中，乘法运算符的两个表达式都是操作数，即(p + q)和(r + s)是操作数。

在上面的表达式中，有三个运算符。第一个加法运算符的操作数是 p 和 q，第二个加法运算符的操作数是 r 和 s。在处理表达式时，我们需要遵循一组规则来评估结果。在上面的表达式中，将对两个表达式 p+q 和 r+s 执行加法运算，然后执行乘法运算。

中缀表示法的语法如下

<操作数> <运算符> <操作数>

如果表达式中只有一个运算符，我们不需要应用任何规则。例如，5 + 2；在这个表达式中，可以在两个操作数（5 和 2）之间执行加法运算，运算结果为 7。

如果表达式中有多个运算符，则需要遵循一些规则来评估表达式。

如果表达式是

4 + 6 * 2

如果先计算加法运算符，则表达式将如下所示

10 * 2 = 20

如果先计算乘法运算符，则表达式将如下所示

4 + 12 = 16

上述问题可以通过遵循运算符优先级规则来解决。在代数表达式中，运算符优先级的顺序如下表所示

首先考虑括号；然后考虑指数。如果存在多个指数运算符，则运算将从右到左应用。

例如

2^2^3 = 2 ^ 8

= 256

指数之后，计算乘法和除法运算符。如果表达式中同时存在这两种运算符，则运算将从左到右应用。

接下来考虑加法和减法。如果表达式中同时存在这两种运算符，则从左到右计算。

具有相同优先级的运算符称为运算符关联性。如果从左到右计算，则称为左关联。如果从右到左计算，则称为右关联。

中缀表示法的问题

要评估中缀表达式，我们需要了解运算符优先级规则，如果运算符具有相同的优先级，则需要遵循关联性规则。括号的使用在中缀表示法中非常重要，用于控制运算执行的顺序。括号提高了表达式的可读性。中缀表达式是最常见的表达式书写方式，但要无歧义地解析和评估中缀表达式并不容易。因此，数学家和逻辑学家研究了这个问题，并发现了另外两种书写表达式的方式：前缀和后缀。这两种表达式都不需要括号，并且可以无歧义地解析。它们不需要运算符优先级和关联性规则。

后缀表达式

后缀表达式是在运算符写在操作数之后的表达式。例如，中缀表达式 ( 2+3) 的后缀表达式可以写成 23+。

关于后缀表达式的一些要点

• 在后缀表达式中，运算按从左到右的顺序执行。
• 它不需要任何括号。
• 我们不需要应用运算符优先级规则和关联性规则。

评估后缀表达式的算法

• 从左到右扫描表达式，直到遇到任何运算符。
• 执行运算
• 用计算值替换表达式。
• 重复步骤 1 到 3，直到不再存在运算符。

让我们通过一个例子来理解上述算法。

中缀表达式：2 + 3 * 4

我们将从表达式的最左边开始扫描。乘法运算符是从左到右扫描时最先出现的运算符。现在，表达式将是

表达式 = 2 + 34*

= 2 + 12

再次，我们将从左到右扫描，表达式将是

表达式 = 2 12 +

= 14

使用栈评估后缀表达式。

• 从左到右扫描表达式。
• 如果在表达式中遇到任何操作数，则将操作数压入栈中。
• 当遇到表达式中的任何运算符时，从栈中弹出相应的操作数。
• 扫描完表达式后，最终值保留在栈中。

让我们通过一个例子来理解使用栈评估后缀表达式。

示例 1：后缀表达式：2 3 4 * +

上述表达式的结果是 14。

示例 2：后缀表达式：3 4 * 2 5 * +

上述表达式的结果是 22。

评估后缀表达式的算法

1. 读取字符
2. 如果字符是数字，则将字符转换为整数并将其压入栈中。
3. 如果字符是运算符，
   • 从栈中弹出两次元素，得到两个操作数。
   • 执行运算
   • 将结果压入栈中。

中缀转后缀转换

在这里，我们将使用栈数据结构将中缀表达式转换为前缀表达式。每当遇到运算符时，我们将运算符压入栈中。如果遇到操作数，则将操作数附加到表达式。

中缀表达式转换为后缀表达式的规则

1. 按到达顺序打印操作数。
2. 如果栈为空或栈顶是左括号，则将传入的运算符压入栈中。
3. 如果传入的符号是 '('，则将其压入栈中。
4. 如果传入的符号是 ')'，则弹出栈并打印运算符，直到找到左括号。
5. 如果传入的符号的优先级高于栈顶，则将其压入栈中。
6. 如果传入的符号的优先级低于栈顶，则弹出并打印栈顶。然后将传入的运算符与新的栈顶进行比较。
7. 如果传入的运算符与栈顶的优先级相同，则使用关联性规则。如果关联性是从左到右，则弹出并打印栈顶，然后压入传入的运算符。如果关联性是从右到左，则压入传入的运算符。
8. 在表达式结束时，弹出并打印栈中的所有运算符。

让我们通过一个例子来理解。

中缀表达式：K + L - M*N + (O^P) * W/U/V * T + Q

中缀表达式(K + L - M*N + (O^P) * W/U/V * T + Q)的最终后缀表达式是 KL+MN*-OP^W*U/V/T*+Q+。