A Calculator which can do basic operations like " + , - , x, / " [LeetCode 224/227/772]

BasicCalculatorRecursion.py

class Solution:
    
    def calculate(self, s: str) -> int:
        
        # Strip and replace all the spaces
        s = s.strip().replace(" ","")
        
        # Evaluate
        def update(stack: List, curr: str, operator: str):
            if curr:
                if operator == "-":
                    stack.append(-1 * int(curr))
                elif operator == "*":
                    n = stack.pop()
                    m = int(curr)
                    stack.append(n*m)
                elif operator == "/":
                    n = stack.pop()
                    m = int(curr)
                    stack.append(int(n/m))
                else:
                    stack.append(int(curr))
            return
        
        # Function to evaluate current
        def evaluate(s: str, idx: int = 0):
            
            stack = []
            operator = ""
            curr = ""
            
            while idx < len(s):
               
                # next char
                char = s[idx]
                
                # End of current expression
                if char == ")":
                    break
                
                # If new expression, evaluate it first
                elif char == "(":
                    v, idx = evaluate(s,idx+1)
                    update(stack, str(v), operator)
                
                # If digit keep on appending
                elif char.isdigit():
                    curr = curr + char
                    
                else: # update stack
                    update(stack, curr, operator)
                    operator = char
                    curr = ""
                
                # increment index
                idx = idx + 1
                
            # Update stack for last operation
            update(stack, curr, operator)
            
            return (sum(stack), idx)
        
        return evaluate(s)[0] 

BasicCalculatorTreeNode.py

# This method is not very efficient, it is just for reference

from collections import deque

# Class describes tree structure
class TreeNode:
    
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
        return
    
class Solution:
    
    # Evaluating the expression tree
    def evaluate(self, root: TreeNode) -> int:
        
        res = 0 # Default value
        
        if root:
            
            # evaluate left subtree
            v_left = self.evaluate(root.left)
            
            # evaluate right subtree
            v_right = self.evaluate(root.right)
            
            # Evaluate root
            v = root.val
            if isinstance(v, TreeNode):
                res = self.evaluate(v)
            else: # Do calculations
                if v == "+":
                    res = int(v_left) + int(v_right)
                elif v == "-":
                    res = int(v_left) - int(v_right)
                else:
                    res = int(v)
                    
        return res
    
    def calculate(self, s: str) -> int:
        
        stack = deque() # Main stack
        stack_aux = deque() # Auxillary stack
        
        # Logic to make stack
        for char in s:
            
            if char == ")": # Closing bracket
                
                # Retrival
                while True: # For expressions like (a-b+c)
                    if stack[-1] == "(": # Opening bracket
                        stack.pop()
                        break
                    else:
                        stack_aux.append(stack.pop())
                
                # Constructions
                if len(stack_aux) > 2: # for expressions like (a+b) or (a-b) or (a-b+c)
                    while True:
                        l = TreeNode(stack_aux.pop())
                        v = stack_aux.pop()
                        r = TreeNode(stack_aux.pop())
                        v = TreeNode(v, l, r)
                        if stack_aux:
                            stack_aux.append(v)
                        else:
                            stack.append(v)
                            break
                elif len(stack_aux) == 2: # for expressions like (-a) 
                    sign = stack_aux.pop()
                    v = stack_aux.pop()
                    stack.append(str(-1*int(v)))
                else: # for expression like (a)
                    v = stack_aux.pop()
                    stack.append(v)
                    
            elif char != ' ': # Not space
                # If digit is 1000 or 13 or 98
                if char.isdigit() and stack and stack[-1].replace("-","").isdigit():
                    stack[-1] += char
                elif char.isdigit() and stack and len(stack) == 1 and stack[-1] == "-": # for expressions like "-a"
                    stack.pop()
                    stack.append(str(-1*int(char)))
                else: # for any other type of char
                    stack.append(char)
        
        
        # Logic to make root of tree node
        root = None
        
        # Case 1
        if len(stack) == 1:
        
            # Case 1A: Single Tree node
            if isinstance(stack[-1], TreeNode): # for expression like "(a+b)"
                root = stack.pop()
            else: # Case 1B: Single Digitn # for expressions like "(a)"
                root = TreeNode(stack.pop())
        
        # Case 2: Single tree node with leading "-"
        elif len(stack) == 2: # For expressions like "-(a+b-c)"
            root = stack.pop()
            return -1 * self.evaluate(root)
        
        # Case 3: All other conditions
        else:
            while True:
                l = TreeNode(stack.popleft())
                v = stack.popleft()
                r = TreeNode(stack.popleft())
                v = TreeNode(v, l, r)
                if stack:
                    stack.appendleft(v)
                else:
                    root = v
                    break
        
        return self.evaluate(root)