algorithm - 将中缀转换为反向波兰表示法(后缀)的方法

Question

除了 Dijkstra 调车场算法之外，还有什么方法可以将中缀转换为 RPN 吗？我试图通过将其与另一种转换方法进行比较来研究调车场算法的弱点和优势。非常感谢调车场算法期刊的任何链接。谢谢

Answer 1

在现实生活中，我总是递归地解析表达式。

在 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 +

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

请注意，上面的代码没有正确处理语法错误。