將中綴轉換爲Reverse Polish Notation（Postfix）的方法

Question

除了Dijkstra分流碼算法將中綴轉換爲RPN之外，有沒有其他方法？我試圖通過將其與另一種轉換方法進行比較來研究分流碼算法的弱點和優點。任何鏈接到分流碼算法的日記非常感謝。謝謝

Answer 1

當然有，LR解析，解析器組合器，可能很多其他kinds of parsers。

Answer 2

在現實生活中，我總是遞歸地解析表達式。

在Python中，基本的算法是這樣的：

import re 
import sys 

def toRpn(infixStr): 
    # divide string into tokens, and reverse so I can get them in order with pop() 
    tokens = re.split(r' *([\+\-\*\^/]) *', infixStr) 
    tokens = [t for t in reversed(tokens) if t!=''] 
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2} 

    #convert infix expression tokens to RPN, processing only 
    #operators above a given precedence 
    def toRpn2(tokens, minprec): 
     rpn = tokens.pop() 
     while len(tokens)>0: 
      prec = precs[tokens[-1]] 
      if prec<minprec: 
       break 
      op=tokens.pop() 

      # get the argument on the operator's right 
      # this will go to the end, or stop at an operator 
      # with precedence <= prec 
      arg2 = toRpn2(tokens,prec+1) 
      rpn += " " + arg2 + " " +op 
     return rpn 

    return toRpn2(tokens,0) 

print toRpn("5+3*4^2+1") 

#prints: 5 3 4 2^* + 1 + 

這種形式很容易適應處理該關聯從右到左，如賦值運算符括號，一元運算符，和運營商。

請注意，上述代碼不能正確處理語法錯誤。