算法目的:给计算机一个中缀表达式,输出一个后缀表达式。
考点:考察进行到某一步时,栈内的情况是怎么样的,选择题。
学习目标:能用笔算的方式模拟整个过程,不需要会写代码。
过程:
-
初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素,直到末尾。可能遇到三种情况:
-
-
遇到操作数。直接加入后缀表达式;
-
遇到界限符。遇到 “(” 直接入栈,遇到 “)” 则依次弹出栈内运算符并加入后缀表达式,直到弹出“)”为止。注意:“(”不加入后缀表达式;
-
遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(”或栈空则停止,之后再把当前运算符入栈。
-
-
最后将栈中剩余运算符依次弹出,并加入后缀表达式。
下图为手推过程,黑笔是栈,红笔是当前扫描的位置,蓝笔是当前后缀表达式。需要注意的是第⑧步中,“-”没有直接出栈是因为暂时不能确定它的运算顺序,比如D后面如果跟个“*”就要先计算后面的,所以要把“-”压入栈。每一步都根据上面说的步骤一一对应找一下理解理解就好了。