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

yipeiwu_com5年前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()

希望本文所述对大家的Python程序设计有所帮助。

相关文章

python的三目运算符和not in运算符使用示例

python的三目运算符和not in运算符使用示例

三目运算符也就是三元运算符 一些语言(如Java)的三元表达式形如: 判定条件?为真时的结果:为假时的结果 result=x if x Python的三元表达式有如下几种书写方法...

Python with用法:自动关闭文件进程

实际上,Python 提供了 with 语句来管理资源关闭。比如可以把打开的文件放在 with 语句中,这样 with 语句就会帮我们自动关闭文件。 with 语句的语法格式如下:...

python scp 批量同步文件的实现方法

该脚本用于将源主机列表路径下的所有文件同步于目标主机的/tmp下面 #!/usr/bin/python # -*- coding:utf-8 -*- import pexpect...

对Python3 pyc 文件的使用详解

什么是pyc文件 pyc是一种二进制文件,是由py文件经过编译后,生成的文件,是一种byte code,py文件变成pyc文件后,加载的速度有所提高,而且pyc是一种跨平台的字节码,是由...

Python序列对象与String类型内置方法详解

本文实例讲述了Python序列对象与String类型内置方法。分享给大家供大家参考,具体如下: 前言 在Python数据结构篇中介绍了Python的序列类型数据结构,这次继续深入的学习序...