执着于理想,纯粹于当下

目录
将中缀表达式转化为后缀表达式
/    

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

我们把平时所用的标准四则运算表达式,即 a*(b+c)-d 叫做中缀表达式。因为所有的运算符号都在两数字的中间,现在我们的问题就是中缀到后缀的转化。
中缀表达式“a*(b+c)-d”转化为后缀表达式“abc+*d-”。

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

下面我们来具体看看这个过程。

1.初始化一空栈,用来对符号进出栈使用。

2.第一个字符是 a,输出 a,后面是符号“*”,进 栈。

image.png

3.第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。

4.第四个字符是 b,输出,总表达式为 ab,接着是“+”进栈。

image.png

5.接下来是 c,输出,总表达式为 abc,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“+”,总的输出表达式为 abc+

image.png

6.紧接着是符号“-”,因为此时的栈顶符号为“*”号,优先级高于“-”,因此输出。

image.png

7.此时是最后一个字符 b,输出,总表达式为 abc+*b

image.png

8.因已经到最后,所以将栈中符号全部出栈并输出,也就是把 “-”输出。最终输出的后缀表达式结果为 abc+*d-。

总结:整个过程,都充分利用了栈的后进先出特性来处理,理解好它其实也就理解好了栈这个数据结构。

拓展:从刚才的推导中你会发现,要想让计算机具有处理我们通常的标准(中缀)表达式的能力,最重要的就是两步:

  1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
  2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

标题:将中缀表达式转化为后缀表达式
作者:JaneChelle
地址:https://xiao.algerfan.cn/articles/2020/03/28/1585389042527.html