逆波兰式，也叫后缀表达式
技巧：为简化代码，引入一个不存在的运算符#，优先级最低。置于堆栈底部
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.5 print(bds1, '=', solve5(solve(bds1))) print(bds2, '=', solve5(solve(bds2))) #print(bds1, '=', eval(bds1)) print(bds2, '=', eval(bds2))
