如何将令牌变成树木（Python）

发布于 2025-02-12 08:41:52 字数 509 浏览 0 评论 0原文

我正在研究一个Python项目，当您用方程式（包括操作员）的一行编写时，它将为您计算方程式。首先，如果我们在字符串中写入，它将将字符串转换为单个令牌。

"12+2*3" -> [ "12", "+", "2", "*", "3" ]

然后，我们将每个令牌更改为一棵树。

[ "12", "+", "2", "*", "3" ]

- ＆gt; [[“ 12”]，“+”，[[“ 2”]，“*”，[3']]]]

[ "(", "2", "+", "3", ")", "*", "7" ]

- ＆gt; [[[[[“ 2”），“+”，[“ 3”]]，“（”，[，[]，“*”，[7']]

代币必须按列表按操作顺序分组，如果有par虫，它一定是[[parantheses内部的数字]，“（”，[，[]]

我在第二部分中遇到麻烦，将令牌覆盖成树。建议我使用一个递归功能，但是如何呢？

原文

I'm working on a python project which when you write in a line of an equation(including operators) it will calculate the equation for you.
First, if we write in a string, it would convert the string into individual tokens.

"12+2*3" -> [ "12", "+", "2", "*", "3" ]

Then, we would change each token into a tree.

[ "12", "+", "2", "*", "3" ]

-> [ ["12"], "+", [["2"], "*", ["3"]] ]

[ "(", "2", "+", "3", ")", "*", "7" ]

->
[[[["2"], "+", ["3"]], "(", []], "*", ["7"]]

Tokens must be grouped by a list in the order of operations, and if there are parantheses, it must be in the form of [[The number inside the parantheses], "(", []]

I am having trouble with the second part, coverting tokens into trees. It is recommended that I use a recursive function, but how?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

心奴独伤 2025-02-19 08:41:52

这是您可以使用的实现：

使用递归
使用字典来定义运算符的优先级
具有一些基本错误处理，因为表达式无效（不平衡括号，一个未知的操作员，...）

def make_tree(lst):
    def report(op):
        op = f"'{op}'" if op else "end-of-input"
        raise ValueError(f"Unexpected {op}")
    
    def read_operand():
        token = next(it, "")
        if token == "(":
            expr, op = read_expression(0)
            if op != ")":
                report(op)
            return [expr, "(", []]
        elif token in precedence:
            report(token)
        return [token]
            
    def read_expression(level):
        left = read_operand()
        op = next(it, "")
        while precedence[op] > level:
            *left, op = [left, op, *read_expression(precedence[op])]
        return left, op

    precedence = {"(": 0, ")": 0, "": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    it = iter(lst)
    expr, op = read_expression(1)
    if op != "":
        report(op)
    return expr
    
print(make_tree(["12","+","2","*","3"]))  # [['12'],'+',[['2'],'*',['3']]]
print(make_tree(["(","2","+","3",")","*","7"]))  # [[[['2'],'+',['3']],'(',[]],'*',['7']]

Here is an implementation you could use:

Uses recursion
Uses a dictionary to define the precedence of operators
Has some basic error handling for when the expression is invalid (unbalanced parentheses, an unknown operator, ...)

def make_tree(lst):
    def report(op):
        op = f"'{op}'" if op else "end-of-input"
        raise ValueError(f"Unexpected {op}")
    
    def read_operand():
        token = next(it, "")
        if token == "(":
            expr, op = read_expression(0)
            if op != ")":
                report(op)
            return [expr, "(", []]
        elif token in precedence:
            report(token)
        return [token]
            
    def read_expression(level):
        left = read_operand()
        op = next(it, "")
        while precedence[op] > level:
            *left, op = [left, op, *read_expression(precedence[op])]
        return left, op

    precedence = {"(": 0, ")": 0, "": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    it = iter(lst)
    expr, op = read_expression(1)
    if op != "":
        report(op)
    return expr
    
print(make_tree(["12","+","2","*","3"]))  # [['12'],'+',[['2'],'*',['3']]]
print(make_tree(["(","2","+","3",")","*","7"]))  # [[[['2'],'+',['3']],'(',[]],'*',['7']]

回复收藏 0 原文

~没有更多了~