本文实例讲述了python实现逆波兰计算表达式的方法。分享给大家供大家参考。具体分析如下：
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家j.lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
# -*- coding: utf-8 -*-
symbol_priority = {}
symbol_priority[0] = [‘#’]
symbol_priority[1] = [‘(‘]
symbol_priority[2] = [‘+’, ‘-‘]
symbol_priority[3] = [‘*’, ‘/’]
symbol_priority[4] = [‘)’]
def comparepriority(symbol, rpn_stack, symbol_stack):
”’compare priority between two symbols”’
global symbol_priority
if len(symbol_stack) > 0:
symbol_pop = symbol_stack.pop()
else:
return
for list in symbol_priority.values():
if (symbol in list) and (symbol_pop in list):
”’same priority”’
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
elif symbol in list:
”’symbol is smaller”’
rpn_stack.append(symbol_pop)
#recusion call
comparepriority(symbol, rpn_stack, symbol_stack)
return
elif symbol_pop in list:
”’symbol is bigger”’
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
else:
continue
symbol_stack.append(symbol_pop)
return
def scaneveryone(input_string, rpn_stack, symbol_stack):
for ch in input_string:
if ch.isdigit():
rpn_stack.append(ch)
else:
if len(symbol_stack) > 0:
if ch == ‘(‘:
symbol_stack.append(ch)
elif ch == ‘)’:
while true:
symbol_pop = symbol_stack.pop()
if symbol_pop == ‘(‘:
break
else:
rpn_stack.append(symbol_pop)
else:
comparepriority(ch, rpn_stack, symbol_stack)
else:
symbol_stack.append(ch)
def scaninput(rpn_stack, symbol_stack):
input_string = raw_input()
input_string += ‘#’
scaneveryone(input_string, rpn_stack, symbol_stack)
def calrpn(rpn_stack):
value_stack = []
rpn_stack.append(‘#’)
for value in rpn_stack:
if value == ‘#’:
return value_stack.pop()
break
if value.isdigit():
value_stack.append(value)
else:
right_value = value_stack.pop()
left_value = value_stack.pop()
cal_string = left_value + value + right_value
value_stack.append(str(eval(cal_string)))
def main():
rpn_stack = []
symbol_stack = []
scaninput(rpn_stack, symbol_stack)
print calrpn(rpn_stack)
if __name__ == ‘__main__’:
main()
calrpn.py
# -*- coding: utf-8 -*-
symbol_priority = {}
symbol_priority[0] = [‘#’]
symbol_priority[1] = [‘(‘]
symbol_priority[2] = [‘+’, ‘-‘]
symbol_priority[3] = [‘*’, ‘/’]
symbol_priority[4] = [‘)’]
def comparepriority(symbol, rpn_stack, symbol_stack):
”’compare priority between two symbols”’
global symbol_priority
if len(symbol_stack) > 0:
symbol_pop = symbol_stack.pop()
else:
return
for list in symbol_priority.values():
if (symbol in list) and (symbol_pop in list):
”’same priority”’
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
elif symbol in list:
”’symbol is smaller”’
rpn_stack.append(symbol_pop)
#recusion call
comparepriority(symbol, rpn_stack, symbol_stack)
return
elif symbol_pop in list:
”’symbol is bigger”’
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
else:
continue
symbol_stack.append(symbol_pop)
return
def scaneveryone(input_string, rpn_stack, symbol_stack):
for ch in input_string:
if ch.isdigit():
rpn_stack.append(ch)
else:
if len(symbol_stack) > 0:
if ch == ‘(‘:
symbol_stack.append(ch)
elif ch == ‘)’:
while true:
symbol_pop = symbol_stack.pop()
if symbol_pop == ‘(‘:
break
else:
rpn_stack.append(symbol_pop)
else:
comparepriority(ch, rpn_stack, symbol_stack)
else:
symbol_stack.append(ch)
def scaninput(rpn_stack, symbol_stack):
input_string = raw_input()
input_string += ‘#’
scaneveryone(input_string, rpn_stack, symbol_stack)
def calrpn(rpn_stack):
value_stack = []
rpn_stack.append(‘#’)
for value in rpn_stack:
if value == ‘#’:
return value_stack.pop()
break
if value.isdigit():
value_stack.append(value)
else:
right_value = value_stack.pop()
left_value = value_stack.pop()
cal_string = left_value + value + right_value
value_stack.append(str(eval(cal_string)))
def main():
rpn_stack = []
symbol_stack = []
scaninput(rpn_stack, symbol_stack)
print calrpn(rpn_stack)
if __name__ == ‘__main__’:
main()
希望本文所述对大家的python程序设计有所帮助。