LeetCode: 1628. Design an Expression Tree With Evaluate Function

 

First thing first: 

To implement an expression tree with "Postfix", we can easily do so with a stack.

 

For the evaluation part:

"ABC" might be a bit unfamiliar, but all you need to know about it here is that you cannot initiate an instance with the ABC class (in this case Node class). 

In addition, an abstract method must be implemented in the child class.

 

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

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

    def evaluate(self):
        if self.val is not None:
            return self.val
        elif self.opt is not None:
            if self.opt == '+':
                return self.left.evaluate() + self.right.evaluate()
            elif self.opt == '-':
                return self.left.evaluate() - self.right.evaluate()
            elif self.opt == '*':
                return self.left.evaluate() * self.right.evaluate()
            elif self.opt == '/':
                return int(self.left.evaluate() / self.right.evaluate())
            else:
                raise(ValueError)
        else:
            raise(ValueError)


"""    
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':
        s = []
        for pf in postfix:
            if pf.isnumeric():
                s.append(TreeNode(int(pf)))
            else:
                node2 = s.pop()
                node1 = s.pop()
                s.append(TreeNode(None, pf, node1, node2))
        return s[0]

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