逆波兰式，也叫后缀表达式
技巧：为简化代码，引入一个不存在的运算符#，优先级最低。置于堆栈底部
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))
转载于:https://www.cnblogs.com/hhh5460/p/5182081.html
相关资源：python实现逆波兰计算表达式实例详解
