中缀表达式转化为后缀表达式的方法-趣百科

中缀表达式转化为后缀表达式的方法

中缀表达式转化为后缀表达式是学习数据结构必须掌握的知识

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

例题：中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式

①初始化一空栈，用来对符号进出栈使用。

②第一个字符是数字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 / +。

将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来

顺序将每对括号中的运算符移到相应括号的后面

删除所有括号

例题：求中缀表达式a*(b+c)-d的后缀表达式

按照上面的方法有：

第一步：((a*((b+c)))-d)

第二步：((a(b c)+))*d)-

第三步：abc+ *d-

中缀表达式转化为后缀表达式的方法