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程序设计有所帮助。

相关文章

浅谈机器学习需要的了解的十大算法

浅谈机器学习需要的了解的十大算法

毫无疑问,近些年机器学习和人工智能领域受到了越来越多的关注。随着大数据成为当下工业界最火爆的技术趋势,机器学习也借助大数据在预测和推荐方面取得了惊人的成绩。比较有名的机器学习案例包括Ne...

python模块smtplib学习

python的smtplib提供了一种很方便的途径发送电子邮件。它对smtp协议进行了简单的封装。 smtp协议的基本命令包括:     HELO 向服务...

Flask框架学习笔记(一)安装篇(windows安装与centos安装)

Flask 依赖于两个外部库: Werkzeug  和  Jinja2  。 Werkzeug 是一个 WSGI (在 web 应用和多种服务器之间开发和部...

wxpython中Textctrl回车事件无效的解决方法

本文实例讲述了wxpython中Textctrl回车事件无效的解决方法。分享给大家供大家参考,具体如下: 今天使用wxptyhon的Textctrl控件开发客户端时遇到了一个问题, 按照...

Python 使用 PyMysql、DBUtils 创建连接池提升性能

Python 使用 PyMysql、DBUtils 创建连接池提升性能

Python 编程中可以使用 PyMysql 进行数据库的连接及诸如查询/插入/更新等操作,但是每次连接 MySQL 数据库请求时,都是独立的去请求访问,相当浪费资源,而且访问数量达到一...