逆波兰式,是编程计算四则运算结果的算法。例子:平时写法a+b(中缀表达式),逆波兰式ab+。
把中缀表达式编程后缀表达式的法则:
首先需要两个栈:s1操作数栈,s2运算符栈。当前取的字符为x。
a.如果x是数字,直接压入s1.
b.如果x是左括号,直接压入s2.
c.如果x是右括号,把它和距离栈顶最近的左括号之前的运算符,依次压入操作数栈。左括号舍弃。
d.如果x是+-*/。如果栈顶是左括号,直接压入s2。否则,如果s2栈顶运算符优先级低于x(不包括等于),x压入s2.否则,依次弹出栈顶,压入s1,直到满足条件为止。
e.重复以上四条。
例子:计算9+(3-1)*3+10/2
s1: 栈底栈顶
s2:栈底栈顶
x=9
s1: 栈底9栈顶
s2:栈底栈顶
x=+
s1: 栈底9栈顶
s2:栈底+栈顶
x=(
s1: 栈底9栈顶
s2:栈底+(栈顶
x=3
s1: 栈底93栈顶
s2:栈底+(栈顶
x=-
s1: 栈底93栈顶
s2:栈底+(-栈顶
x=1
s1: 栈底931栈顶
s2:栈底+(-栈顶
x=)
s1: 栈底931栈顶
s2:栈底+(-栈顶
-从s2弹出,压入s1.
s1: 栈底931-栈顶
s2:栈底+栈顶
s1中出现运算符,要计算
s1: 栈底92栈顶
s2:栈底+栈顶
x=*
s1: 栈底92栈顶
s2:栈底+栈顶
x=3
s1: 栈底923栈顶
s2:栈底+栈顶
x=+
把=依次从s2弹出压入s1
s1: 栈底923栈顶
s2:栈底+栈顶
s1: 栈底96栈顶
s2:栈底+栈顶
s1: 栈底96+栈顶
s2:栈底栈顶
s1: 栈底15栈顶
s2:栈底+栈顶
x=10
s1: 栈底15 10栈顶
s2:栈底+栈顶
x=/
s1: 栈底15 10栈顶
s2:栈底+/栈顶
x=2
s1: 栈底15 10 2栈顶
s2:栈底+/栈顶
最后,s2依次出栈,压入s1
s1: 栈底15 5栈顶
s2:栈底+栈顶
s1: 栈底20栈顶
s2:栈底栈顶
写在最后的话:知识要弄懂,再简单也要下苦工。
网友评论