1628. Design an Expression Tree With Evaluate Function

Updated: 2024-03-12
1 min read

On This Page

LeetCode problem 1628

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):
    # define your fields here
    def evaluate(self) -> int:

class MyNode(Node):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def evaluate(self) -> int:
        x = self.val
        if x.isdigit():
            return int(x)

        left, right = self.left.evaluate(), self.right.evaluate()
        if x == '+':
            return left + right
        if x == '-':
            return left - right
        if x == '*':
            return left * right
        if x == '/':
            return left // right

This is the TreeBuilder class.
You can treat it as the driver code that takes the postinfix input
and returns the expression tree represnting it as a Node.

class TreeBuilder(object):
    def buildTree(self, postfix: List[str]) -> 'Node':
        stk = []
        for s in postfix:
            node = MyNode(s)
            if not s.isdigit():
                node.right = stk.pop()
                node.left = stk.pop()
        return stk[-1]

Your TreeBuilder object will be instantiated and called as such:
obj = TreeBuilder();
expTree = obj.buildTree(postfix);
res = expTree.evaluate();