计算机是如何理解表达式的？从中缀到后缀一文搞定！

表达式

在学习数据结构和算法时，我们常常会接触到表达式的不同写法，它们分别是中缀表达式、前缀表达式和后缀表达式。我们日常最熟悉的表达形式就是中缀表达式，如下所示：

5-4\*3/(2+1)

中缀表达式最符合人类的书写和阅读习惯，但对于计算机来说，它却并不友好。于是，为了更高效地进行计算，我们引入了前缀和后缀表达式的表示方式。

一、中缀表达式

中缀表达式是我们平时学习和使用的表达方式，它的特点是：运算符位于两个操作数之间，并且可以通过括号来调整运算优先级。

虽然中缀表达式易于阅读，但它存在如下问题：

• 运算顺序不明确，依赖运算符优先级与括号；
• 结构不够线性，计算过程复杂，不适合计算机直接解析。

中缀表达式的计算（借助两个栈）

为了让计算机也能处理中缀表达式，我们可以借助两个栈：

栈1（操作数栈）：用于保存操作数；

栈2（运算符栈 ：用于保存运算符。

基本步骤如下：

1. 从左至右遍历表达式；
2. 遇到操作数，入栈1；
3. 遇到运算符，比较其优先级：

如果栈2为空，或当前运算符优先级大于栈顶运算符，入栈；

否则弹出栈2顶端运算符，同时从栈1中弹出两个操作数进行运算，将结果压入栈1，然后继续比较；

1. 遇到左括号直接入栈，遇到右括号则不断弹出栈2并计算，直到遇到左括号；
2. 遍历结束后，如果栈2不为空，继续弹出并计算，直到栈清空；

最终栈1中的元素即为表达式的计算结果。

流程如下：

二、前缀表达式

前缀表达式又称波兰表达式，其特点是：运算符写在两个操作数的前面，如下所示：

-5\*4/3+12

该前缀表达式所对应的中缀表达式是

5-4\*3/(2+1)

前缀表达式的优势在于，完全不依赖括号或运算符优先级来确定运算顺序。按照从右往左的顺序遍历，先遇到的运算符先进行运算。

前缀表达式的计算方式（借助栈）：

1. 初始化一个栈 stack；
2. 从右往左遍历表达式；
3. 遇到数字，压入栈；
4. 遇到运算符，弹出栈顶的两个数字，执行运算后将结果压入栈；
5. 重复上述过程，直到遍历完成；
6. 栈顶的数字即为最终结果。

三、后缀表达式（重点）

后缀表达式也叫逆波兰表达式，其特点是：运算符写在两个操作数之后，比如：

54321+/\*-

该后缀表达式所对应的中缀表达式同样是

5-4\*3/(2+1)

后缀表达式的优势

• 不需要括号；
• 运算顺序唯一且明确；
• 更加贴近计算机的处理方式。

后缀表达式的计算方式：

1. 初始化一个栈 stack；
2. 从左至右遍历表达式；
3. 遇到数字，压入栈；
4. 遇到运算符，从栈顶弹出两个数字，执行运算后将结果压入栈；
5. 重复上述操作，直到遍历结束；
6. 栈顶元素即为最终计算结果。

流程图如下：

最后栈中剩下的值就是最终的计算结果。

总结

从计算机处理的角度来看，前缀和后缀表达式具有更明确的结构和更线性的执行流程，只需借助一个栈即可完成整个表达式的计算过程。而在实际应用中，由于后缀表达式的运算更加直观简洁，因此它被更广泛地用于计算机内部的表达式求值中。