设计带解析函数的表达式树

难度: Medium

Submission

运行时间: 32 ms

内存: 0.0 MB

import abc 
from abc import ABC, abstractmethod 
"""
This is the interface for the expression tree Node.
You should not remove it, and you can define some classes to implement it.
"""

class Node(ABC):
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val
     
	 
    def evaluate(self) -> int:
        node = self
        if node.val.isdigit():
            return int(node.val)
        
        left_val = node.left.evaluate()
        right_val = node.right.evaluate()
        
        if node.val == '+':
            return left_val + right_val
        
        if node.val == '-':
            return left_val - right_val
        
        if node.val == '*':
            return left_val * right_val
        
        if node.val == '/':
            return left_val // right_val
        

class TreeBuilder(object):
    def buildTree(self, postfix: List[str]) -> 'Node':
        self.i = len(postfix)-1
        return self.helper(postfix)
    
    def helper(self, postfix):
        if self.i < 0:
            return
        
        curr_ch = postfix[self.i]
        node = Node(curr_ch)
        self.i -= 1
        
        if curr_ch.isdigit():
            return node
        
        node.right = self.helper(postfix)
        node.left = self.helper(postfix)
        return node

Explain

这个题解是基于后缀表达式 (逆波兰表示法) 构建表达式树的方法，并提供了一个节点接口 Node 来计算表达式树的值。首先定义了一个抽象基类 Node，每个节点有左右子节点和节点值。节点值可以是数字或者操作符('+', '-', '*', '/')。如果节点值是数字，则直接返回该值；如果是操作符，则递归地计算左右子节点的值并执行相应的运算。TreeBuilder 类中的 buildTree 方法接受后缀表达式的数组，使用递归的方式从后向前读取数组元素，构建表达式树。如果当前元素是数字，则直接创建节点；如果是操作符，则先递归构建右子树和左子树，因为在后缀表达式中，操作符总是跟在对应的操作数之后。

时间复杂度: O(n)

空间复杂度: O(n)

import abc
from abc import ABC, abstractmethod

# 定义表达式树节点的抽象基类
class Node(ABC):
    def __init__(self, val):
        self.left = None # 左子节点
        self.right = None # 右子节点
        self.val = val # 节点值
    
    # 计算当前节点代表的表达式的值
    def evaluate(self) -> int:
        if self.val.isdigit(): # 如果是数字，直接返回其整数值
            return int(self.val)
        
        # 递归计算左右子节点的值
        left_val = self.left.evaluate()
        right_val = self.right.evaluate()
        
        # 根据当前节点的操作符，执行相应的运算
        if self.val == '+':
            return left_val + right_val
        if self.val == '-':
            return left_val - right_val
        if self.val == '*':
            return left_val * right_val
        if self.val == '/':
            return left_val // right_val
        
# 构建表达式树的类
class TreeBuilder(object):
    def buildTree(self, postfix: List[str]) -> 'Node':
        self.i = len(postfix)-1
        return self.helper(postfix)
    
    def helper(self, postfix):
        if self.i < 0:
            return
        
        curr_ch = postfix[self.i] # 当前处理的字符
        node = Node(curr_ch) # 创建新节点
        self.i -= 1
        
        if curr_ch.isdigit(): # 如果是数字，直接返回该节点
            return node
        
        # 如果是操作符，先递归构建右子树和左子树
        node.right = self.helper(postfix)
        node.left = self.helper(postfix)
        return node

Explore

后缀表达式（逆波兰表示法）的设计使得每个操作符直接跟随其操作数，因此从后向前读取时，最先遇到的操作符可以直接应用于其紧接着的操作数。这种从后向前的构造方式符合栈的后进先出（LIFO）原则，使得构建表达式树时可以更自然地处理操作符和操作数的关系，无需额外的数据结构来暂存未处理的操作符。

在构建表达式树时，如果按照正确的后缀表达式规则，每个操作符之前应该有足够的操作数。构建过程中，每遇到一个操作符，就会连续从栈（或递归过程中的调用栈）中取出两个已构建的子树（或节点）作为该操作符的右子节点和左子节点。如果在操作符处理时不能正确地取出两个节点，这通常意味着后缀表达式本身不符合规范。

非法的后缀表达式，如操作符和操作数比例不当，应在构建树之前或构建过程中检测并处理。可以通过跟踪操作数和操作符的数量来验证表达式的有效性。例如，最终操作数数量应该比操作符数量多一个。如果在构建过程中出现不匹配情况，如操作符无法找到足够的操作数，应抛出错误或返回特定的错误信息，指示表达式不合法。

如果后缀表达式中涉及的计算预期结果为非整数，则使用整数除法`//`可能不合适，因为它会导致结果向下取整，从而可能与预期结果不符。在这种情况下，应根据实际需求调整节点类中除法的实现，可能需要使用浮点除法`/`来确保得到精确的小数结果。此外，还应考虑除数为零的错误处理和浮点数精度问题。