一、概要
中綴表達式是我們經常接觸的算術表達式,如(a+b)* c,a * (c - d)等,優點是便于記憶,缺點是對運算順序有嚴格的要求。字尾表達式又稱逆波蘭式,如abc*+d e *f+g*+,雖然不便記憶,但是它不像中綴表達式,對于運算的順序是沒有要求,可以按照順序掃描的方法計算表達式,是以在計算機内部容易用程式設計的方式實作表達式的求值。
二、中綴轉字尾
# !/usr/bin/python
# coding=utf-8
# 中綴表達式轉字尾表達式
# input: 中綴表達式
# output: 字尾表達式
def infix_to_suffix(inf):
stack = []
suf = ""
pt = i = -1
slen = len(inf) - 1
# {"operator" : "priority"}
opt_dict = {"(":3, ")":3, "+":1, "-":1, "*":2, "/":2}
while i < slen:
i += 1
char = inf[i]
if char not in opt_dict.keys():
suf += char.strip()
continue
# pop element util find '(' which should also be pop from stack
if char == ")":
while pt >= 0:
if stack[pt] == "(":
del stack[pt]
pt = pt - 1
break
suf += stack[pt]
del stack[pt]
pt = pt - 1
continue
# pop element whose level less than pri (priority)
# obviously, if is '(', 'break' make effect instantly
pri = opt_dict[char]
while pt >= 0:
if opt_dict[stack[pt]] < pri or stack[pt] == '(':
break
suf += stack[pt]
del stack[pt]
pt = pt - 1
stack.append(char.strip())
pt += 1
# output remainder of stack if possible
suf += "".join(stack)
return suf
def main():
inf = "a+b*c+(d*e+f)*g"
#inf = "a+b*c+(d*e+f)"
#inf = "(a+b)*(c*(d+e))"
suf = infix_to_suffix(inf)
print(suf)
if __name__ == '__main__':
main()
幾點說明
- stack是一個清單,用來模拟棧,pt 訓示棧頂;
- 不同運算符的優先級不同,相應的操作亦不同,詳見注釋;
- suf 表示最終輸出的字尾表達式;
- 跳過空格,是以需要調用strip();
- 為友善起見,僅将“+,-,*,/”四種運算符和“()”考慮在内;
三、字尾轉中綴
字尾轉中綴相對比較簡單。大緻過程為:初始化一個空棧,然後順序掃描表達式,如果不是運算符則壓棧,否則從棧中相繼彈出兩個元素通過運算符做運算,并将運算後的表達式壓棧。
# !/usr/bin/python
# coding=utf-8
# 字尾轉中綴
# input: 字尾表達式
# output: 中綴表達式
def suffix_to_infix(suf):
opt_lst = ['+','-','*','/']
i = p = -1
explen = len(exp) - 1
stack = []
while i < explen:
i += 1
if exp[i] == ' ':
continue
if exp[i] in opt_lst:
# pop stack[p] and stack[p-1]
e1 = stack[p]
del stack[p]
p = p - 1
e2 = stack[p]
del stack[p]
p = p - 1
if exp[i] == "+" or exp[i] == "-":
e = str("(" + e2 + exp[i] + e1 + ")")
else:
e = str(e2 + exp[i] + e1)
p += 1
stack.append(e)
else:
# push to stack top
stack.append(exp[i])
p += 1
return stack[0]
def main():
#suf = "ab+cde+**"
suf = "abc*+de*f+g*+"
inf = suffix_to_infix(suf)
print(inf)
if __name__ == '__main__':
main()
說明:當發現“+,-”運算符時,對彈出的兩個元素做運算後需要加上"()",這是為了保持原有的中綴表達式的運算優先級。可能會加一些多于的"()",但是運算不至于出錯,此處可以優化,隻是為了示範棧的應用沒有實作。