逆波兰表达式
逆波兰表示法即后缀表达式,而后缀表达式需要注意:
①遵循从外向内进行分析
②由算数优先符从低到高进行拆分,例如:
我们以“-”号作为分隔进行拆分,而不是以“*”号
来看一个例题
首先
原式子:E1*E2 变为后缀表达式:E1E2*,同理可得:
最终,将分解的式子带回:
再举一个例子:
①a-(-b)*c=aE1-
②E1=(-b)*c= (-b) c* = b @ c *(求负运算表示为@)
③后缀表达式=a b @ c * -
再再举个例子:
表达式a:=a+b*c↑(d/e)/f的逆波兰表示为
aabcde/↑*f/+:=
含有布尔运算符的逆波兰表达式:
注意下面这道例题:
表达式-atb*c+d+(e*f)/d*e,如果优先级由高到低依次为-、+、*、/,且均为左结合,则其后缀式为 ( D )。
A、abc*+d+ef*d/e*+-
B、a-bc*def*d/e*+++
C、a-bc*+def*d/e*++
D、a-b+cd+ef*+*de*/
如果按照我们上面的方法进行计算,答案应为B,但是这里的优先级为"-,+,*,/",所以我们这里的计算(以优先级低的作为分割):
所以选择答案D
四元式
四元式和逆波兰表达式的过程相反,是由内到外进行计算:
第一步是*,参与运算的符号是B,D,命名为t1,以此类推
例:
写出算术表达式A+B*(C-D)+E/(C-D)**N 的四元式:
(C,D,-,t1)
(B,t1,*,t2)
(A,t2,+,t3)
(C,D,-,t4)
(t4,N,**,t5)
(E,t5,/,t6)
(+,t3,t6,t7)
三元式
三元式与四元式对比,如下:
将四元式的最后一列去掉,并且将t4 转为 4
例子:写出算术表达式A+B*(C-D)+E/(C-D)**N 的三元式:
(C,D,-)
(B,1,*)
(A,2,+)
(C,D,-)
(4,N,**)
(E,5,/)
(3,6,+)
间接三元式
如下图所示的四元式中(1)和(4)重复了
可以将(4)去掉,而其后的(5),(6),(7)就变为(4),(5),(6)
原式中的(5)(^ (4) N),则为(4)(^ (1)N)