Skip to content
第3章

3.7 栈的应用:后缀表达式求值 ​

读到哪算到哪 ​

3.6节说过,后缀式读的顺序就是计算的顺序,人从左往右就能读出它的值。现在让程序来算。

学完这一节,你能写出一个函数,读进一个后缀式,算出它的值。接上3.6节的ToPostfix,就是一个计算器。

本节问题
程序怎么从左往右读一遍后缀式,就算出它的值?

从左往右读3 4 2 * +,看看程序怎么算。

读到3、4、2,都是数,先放着。读到*,它要用哪两个数?是4和2,最后放下的那两个。算出8,放回去,等着后面用。读到+,要用的是3和8,又是最后放下的那两个。算出11。

每个运算符要用的,总是最近放下的两个数。最近的先用,就是后进先出。所以用一个栈放数:

空栈
开始
3栈顶 →
读到 3入栈
34栈顶 →栈底 →
读到 4入栈
342栈顶 →栈底 →
读到 2入栈
38栈顶 →栈底 →
读到 *弹出 2、4,算出 8 入栈
11栈顶 →
读到 +弹出 8、3,算出 11 入栈

读完了,栈里只剩一个数11,它就是结果。

写成伪代码:

text
InitStack(S)
for 后缀式里的每个字符 c:
    if c 是数字:
        Push(S, c 代表的数)
    else:                          // c 是运算符
        Pop(S, &b)                 // 先弹出的是右边的数
        Pop(S, &a)                 // 再弹出左边的数
        Push(S, a c b)             // 算好放回去
Pop(S, &result)
return result

和3.5节对照:括号匹配的栈里放的是"还没配上的左括号",这里放的是"还没用上的数"。都是先放着,等后面的东西来取最近的那一个。3.6节转换时,栈里放的是"还没写出去的运算符"。

选中正文里的任意文字,就可以针对它发表评论