逆波兰表达式是编译原理中的一种基本表达式，利用Python语言也可以实现逆波兰表达式的输出，这里举例实践说明：
什么是逆波兰表达式？
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
举例实现：
#-*-coding:utf-8-*-
symbol_priority={}
symbol_priority[0]=['#']
symbol_priority[1]=['(']
symbol_priority[2]=['+','-']
symbol_priority[3]=['*','/']
symbol_priority[4]=[')']
defcomparePriority(symbol,RPN_stack,symbol_stack):
'''Compareprioritybetweentwosymbols'''
globalsymbol_priority
iflen(symbol_stack)>0:
symbol_pop=symbol_stack.pop()
else:
return
forlistinsymbol_priority.values():
if(symbolinlist)and(symbol_popinlist):
'''samepriority'''
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
elifsymbolinlist:
'''symbolissmaller'''
RPN_stack.append(symbol_pop)
#recusioncall
comparePriority(symbol,RPN_stack,symbol_stack)
return
elifsymbol_popinlist:
'''symbolisbigger'''
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
else:
continue
symbol_stack.append(symbol_pop)
return
defscanEveryone(input_string,RPN_stack,symbol_stack):
forchininput_string:
ifch.isdigit():
RPN_stack.append(ch)
else:
iflen(symbol_stack)>0:
ifch=='(':
symbol_stack.append(ch)
elifch==')':
whileTrue:
symbol_pop=symbol_stack.pop()
ifsymbol_pop=='(':
break
else:
RPN_stack.append(symbol_pop)
else:
comparePriority(ch,RPN_stack,symbol_stack)
else:
symbol_stack.append(ch)
defscanInput(RPN_stack,symbol_stack):
input_string=raw_input()
input_string+='#'
scanEveryone(input_string,RPN_stack,symbol_stack)
defcalRPN(RPN_stack):
value_stack=[]
RPN_stack.append('#')
forvalueinRPN_stack:
ifvalue=='#':
returnvalue_stack.pop()
break
ifvalue.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)))
defmain():
RPN_stack=[]
symbol_stack=[]
scanInput(RPN_stack,symbol_stack)
printcalRPN(RPN_stack)
if__name__=='__main__':
main()
#-*-coding:utf-8-*-
symbol_priority={}
symbol_priority[0]=['#']
symbol_priority[1]=['(']
symbol_priority[2]=['+','-']
symbol_priority[3]=['*','/']
symbol_priority[4]=[')']
defcomparePriority(symbol,RPN_stack,symbol_stack):
'''Compareprioritybetweentwosymbols'''
globalsymbol_priority
iflen(symbol_stack)>0:
symbol_pop=symbol_stack.pop()
else:
return
forlistinsymbol_priority.values():
if(symbolinlist)and(symbol_popinlist):
'''samepriority'''
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
elifsymbolinlist:
'''symbolissmaller'''
RPN_stack.append(symbol_pop)
#recusioncall
comparePriority(symbol,RPN_stack,symbol_stack)
return
elifsymbol_popinlist:
'''symbolisbigger'''
symbol_stack.append(symbol_pop)
symbol_stack.append(symbol)
return
else:
continue
symbol_stack.append(symbol_pop)
return
defscanEveryone(input_string,RPN_stack,symbol_stack):
forchininput_string:
ifch.isdigit():
RPN_stack.append(ch)
else:
iflen(symbol_stack)>0:
ifch=='(':
symbol_stack.append(ch)
elifch==')':
whileTrue:
symbol_pop=symbol_stack.pop()
ifsymbol_pop=='(':
break
else:
RPN_stack.append(symbol_pop)
else:
comparePriority(ch,RPN_stack,symbol_stack)
else:
symbol_stack.append(ch)
defscanInput(RPN_stack,symbol_stack):
input_string=raw_input()
input_string+='#'
scanEveryone(input_string,RPN_stack,symbol_stack)
defcalRPN(RPN_stack):
value_stack=[]
RPN_stack.append('#')
forvalueinRPN_stack:
ifvalue=='#':
returnvalue_stack.pop()
break
ifvalue.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)))
defmain():
RPN_stack=[]
symbol_stack=[]
scanInput(RPN_stack,symbol_stack)
printcalRPN(RPN_stack)
if__name__=='__main__':
main()