将中缀转换为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 + 

这种形式很容易适应处理该关联从右到左，如赋值运算符括号，一元运算符，和运营商。

请注意，上述代码不能正确处理语法错误。