python - 通过插入括号进行运算符优先级解析

Question

我一直在努力尝试将运算符优先级添加到我一直在编写的名为 [mio-lang 1的小玩具实验性编程语言中来自 FreeNode 上的#io 频道的 jer 之类的赞！

我正在尝试将括号插入到正确位置的令牌流中，并且我相信该算法称为自顶向下下降解析器，除非我在这里使用堆栈而不是递归函数调用。

以下是真实事物的幼稚剪辑片段：

from collections import OrderedDict


operators = OrderedDict([
    ("*", (2)), ("/", (2)),
    ("+", (1)), ("-", (1)),
])


def precedence(tokens):
    lparen = "("
    rparen = ")"

    level = None
    levels = []
    output = []

    while tokens:
        if len(tokens) > 1 and tokens[1] == "=":
            return tokens[:2] + precedence(tokens[2:])
        else:
            if len(tokens) > 1 and tokens[1] in operators:
                level = operators.get(tokens[1])

                if levels:
                    if level > levels[-1]:
                        levels.append(level)
                        output.append(lparen)
                else:
                    levels.append(level)

            output.append(tokens.pop(0))
            while levels and level < levels[-1]:
                level = levels.pop()
                output.append(rparen)

    while len(levels) > 1:
        level = levels.pop()
        output.append(rparen)

    return output

这个片段的完整源代码加上一些单元测试可以在这里找到：http ://codepad.org/2yNEp2Pr

非常感谢在修复我的功能和任何边缘情况方面的帮助！