python实现逆波兰计算表达式实例详解

本文实例讲述了python/' target='_blank'>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)    returndef 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)    returndef 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程序设计有所帮助。