基于栈的中缀表达式转后缀表达式

表达式转换

例：A+BC 是中缀表达式，它的后缀表达式为：ABC+

思路

遇到字母或者数字，直接输出。遇到运算符，先 push 到一个栈里，等遇到下一个运算符，和前一个比较一下，前一个优先级高的，就 pop 出去，把后来的 push 进去。后一个优先级高的，把他 push 到栈里。最后，再把栈里元素全部输出。

栈定义函数

class Stack(object):
   def __init__(self):
      self.item = []
      
   def isEmpty(self):
      return self.item == []
      
   def push(self, data):
      self.item.append(data)
      
   def pop(self):
      return self.item.pop()
      
   def peek(self):
      return self.item[len(self.item) - 1] # 返回栈顶元素
      
   def search(self, x): 
      return self.item.index(x)
      
   def size(self):
      return len(self.item)

转换函数

def infix2Postfix(s):
   # 优先级定义
   prec = {}
   prec['/'] = 3
   prec['*'] = 3
   prec['+'] = 2
   prec['-'] = 2
   prec['('] = 1
   
   stack = Stack()
   result = []
   tokenList = s.split()
   for token in tokenList:
       if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '1234567890':
           result.append(token)
       elif token == '(':
           stack.push(token)
       elif token == ')':
           topToken = stack.pop()
           while(topToken != '('):
               result.append(topToken)
               topToken = stack.pop()
       else:
            while(not stack.isEmpty() and (prec[stack.peek()] >= prec[token])):
                result.append(stack.pop())
            stack.push(token)
   while(not stack.isEmpty()):
       result.append(stack.pop())
   return ' '.join(result)

注意：输入格式应为 A + B * C（操作数之间需有空格）。