• 技术文章 >Python技术 >Python高级

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

    PythonPython2019-06-15 11:13:13原创3547
    逆波兰表达式是编译原理中的一种基本表达式,利用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脚本绘制验证码 下一篇:Python解析nginx日志示例

    相关文章推荐

    • 举例详解Python中的内建模块collections• Python中怎么像PS一样处理图像• Python中lambda和def有什么区别

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网