逆波兰式，也叫后缀表达式
技巧：为简化代码，引入一个不存在的运算符#，优先级最低。置于堆栈底部
class Stack(object):
'''堆栈'''
def __init__(self):
self._stack = [] def pop(self):
return self._stack.pop() def push(self, x):
self._stack.append(x)
一、表达式无括号
def solve(bds):
'''不带括号，引入#运算符'''
pro = dict(zip('^*/+-#', [3,2,2,1,1,0]))
out = []
s = Stack()
s.push('#')
for x in bds:
if x in '^*/+-':
t = s.pop()
while pro[x] <= pro[t]:
out.append(t)
t = s.pop() s.push(t)
s.push(x)
else:
out.append(x) while not s.is_null():
out.append(s.pop()) return out[:-1]
bds1 = 'a+b/c^d-e' # abcd^/+e-
print(bds1, ''.join(solve(bds1)))
二、表达式有括号
def solve(bds):
'''带括号，引入#运算符'''
pro = dict(zip('^*/+-#', [3,2,2,1,1,0]))
out = []
s = Stack()
s.push('#')
for x in bds:
if x == '(': # ①左括号 -- 直接入栈
s.push(x)
elif x == ')': # ②右括号 -- 输出栈顶，直至左括号(舍弃)
t = s.pop()
while t != '(':
out.append(t)
t = s.pop()
elif x in '^*/+-': # ③运算符 -- 从栈顶开始，优先级不小于x的都依次弹出；然后x入栈
while True:
t = s.pop()
if t == '(': # 左括号入栈前优先级最高，而入栈后优先级最低！
s.push(t)
break
if pro[x] <= pro[t]:
out.append(t)
else:
s.push(t)
break
s.push(x)
else: # ④运算数 -- 直接输出
out.append(x) while not s.is_null():
out.append(s.pop()) return out[:-1]bds1 = 'a+b/c^d-e' # abcd^/+e-
bds2 = '(a+b)*c-(d+e)/f' # ab+c*de+f/-print(bds1, ''.join(solve(bds1)))
print(bds2, ''.join(solve(bds2)))
三、根据后缀表达式求值
def solve5(bds):
'''根据后缀表达式求值'''
jishuan = {
'^': lambda x,y: x**y,
'*': lambda x,y: x*y,
'/': lambda x,y: x/y,
'+': lambda x,y: x+y,
'-': lambda x,y: x-y
}
s = Stack()
for x in bds:
if x in '^*/+-':
num2, num1 = s.pop(), s.pop()
r = jishuan[x](float(num1), float(num2))
s.push(r)
else:
s.push(x) return s.pop()bds1 = '2+9/3^2-5' # 2932^/+5- -2
bds2 = '(1+2)*3-(4+5)/6' # ab+c*de+f/- 7.5print(bds1, '=', solve5(solve(bds1)))
print(bds2, '=', solve5(solve(bds2)))#print(bds1, '=', eval(bds1))
print(bds2, '=', eval(bds2))
