如何将中缀表达式转换成后缀表达式/后缀表达式的计算
Alter_Native
·
2023-11-28 22:10:05
·
个人记录
\texttt{\textcolor{#FFC408}{How\;to\;translate\;Infix\;to\;Postfix\;}}
\texttt{\textcolor{#FFC408}{And\;calculate\;Postfix?}}
（就是中缀表达式转后缀表达式+后缀表达式的计算）
中缀表达式
中缀表达式（Infix expression）是人类生活中常用的一种表达式，比如：
(3+2)\times 5
大家都知道应该先算 3+2，再把这个结果乘 5。但是，对于计算机来说，这是一种非常复杂的结构，于是就有了：
后缀表达式
后缀表达式（Postfix expression），又叫逆波兰表达式，是一种把运算符放在两个运算数后面的表达式，如：
ab+c*
这在我们看来可能是一个混乱的结构，但计算机就能轻而易举的识别它并完成计算。
中缀表达式转后缀表达式
假设这里有一个字符串，存储了中缀表达式。
首先，我们需要一个符号栈来辅助运算。
一个字符一个字符地遍历它，对每个字符执行以下操作：
如果是运算数，则直接输出到后缀表达式中。
如果是左括号，则直接压入符号栈中。
如果是右括号，则按顺序弹出符号栈中的符号，输出到后缀表达式中，直到遇到左括号（左括号也要弹出，但不输出到后缀表达式，右括号不入栈）。
如果是运算符，则按顺序弹出符号栈中比它优先级高或相同的符号，输出到后缀表达式中，直到遇到比它优先级低的符号，此时运算符直接入栈。（如果栈为空则直接入栈）
运算符的优先级是：左括号优先级最低，加减其次，乘除最高。
如果你的中缀表达式语法正常，转化完成后，符号栈应为空。
我们来举个例子：
3+(2+5\times4)\div11
第一个是运算数 3，直接输出到后缀表达式中。
后缀表达式： 3
第二个是运算符 +，因为符号栈空，所以直接入栈。
后缀表达式： 3
符号栈：+
第三个是左括号，直接入栈。
后缀表达式： 3
符号栈：+\quad(
第四个是运算数，直接输出到后缀表达式中。
后缀表达式： 32
符号栈：+\quad(
第五个是运算符 +，因为左括号优先级低于加号，所以直接入栈。
后缀表达式： 32
符号栈：+\quad(\quad+
第六个是运算数，直接输出。
后缀表达式： 325
符号栈：+\quad(\quad+
第七个是运算符 \times，因为加号优先级小于乘号，所以直接入栈。
后缀表达式： 325
符号栈：+\quad(\quad+\quad\times
第八个是运算数，直接输出。
后缀表达式： 3254
符号栈：+\quad(\quad+\quad\times
第九个是右括号，我们弹出左括号上的所有符号，输出到后缀表达式中。
后缀表达式： 3254\times+
符号栈：+
第十个是操作符 \div，因为除号优先级高于加号，所以除号直接入栈。
后缀表达式： 3254\times+
符号栈：+\quad\div
第十一个是运算数，直接输出。
后缀表达式： 3254\times+11
符号栈：+\quad\div
最后，将栈内符号全部弹出，并输出到后缀表达式中。
后缀表达式： 3254\times+11\div+
转换完成。
后缀表达式的计算
计算后缀表达式比较简单，我们从左到右遍历后缀表达式：
首先，准备一个用来存放数字的栈:
如果遇到数字，则将其压入栈中；
如果遇到运算符，则从栈中弹出两个数字，根据运算符进行计算，并将计算结果压入栈中。（栈顶元素在前计算）
直到扫描完整个后缀表达式，最后栈中只剩下一个元素，就是后缀表达式的计算结果。
举个例子，我们刚才的后缀表达式：
3254\times+11\div+
读入3，将其压入栈中；
读入2，将其压入栈中；
读入5，将其压入栈中；
读入4，将其压入栈中；
读入\times，从栈中弹出4和5，计算4\times5得到20，并将20压入栈中；
读入+，从栈中弹出2和20，计算2+20得到22，并将22压入栈中；
读入11，将其压入栈中；
读入\div，从栈中弹出11和22，计算22\div11得到2，并将2压入栈中；
读入+，从栈中弹出3和2，计算3+2得到5，并将5压入栈中；
最后栈中只剩下一个元素5，它就是后缀表达式的计算结果。
因此，后缀表达式3254×+11\div+的值为5。