用Python举例实现逆波兰表达式

逆波兰表达式是编译原理中的一种基本表达式，利用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()