772. Basic Calculator III

reference: https://www.geeksforgeeks.org/expression-evaluation/

Notes:

converting infix notation (eg 3+4) to prefix notation (eg + 3 4) or post notation 1.1 eg using 2 separate stacks for operators and numbers
if digit: scan the entire number and push to number stack
if (: push to op stack
if ): evaluate the result in between ()
- 4.1 operator at the top of op stack is guaranteed to have high priority compared with the previous operator in the op stack
if any other operator:
- 5.1 look back one operator in stack to decided if the previous operator needs to be evaluated
- 5.2 evaluate the previous op only if the previous op has higher priority compared with current op
- 5.3 otherwise, leave the previous op to be evaluated by step 4 (ie current op has higher priority than previous op)
- 5.4 step 3 should not be merged into step 5: evaluation here should only be applied to binary operator (ie +-*/). Imagining we process "(3+5)" here so we would pop from empty num stack when i is pointing to (
taking care of floor division (eg 8/(-7) = -2 but we want it to be -1)

class Solution:
    def calculate(self, tokens: str) -> int:
        values = []
        ops = []
        i = 0
     
        while i < len(tokens):
            if tokens[i] == ' ':
                i += 1
                continue
            elif tokens[i] == '(':
                ops.append('(')
            elif tokens[i].isdigit():
                val = 0
                while (i < len(tokens) and tokens[i].isdigit()):
                    val = (val * 10) + int(tokens[i])
                    i += 1
                values.append(val)
                i -= 1 # correct the offset
            elif tokens[i] == ')':
                while len(ops) != 0 and ops[-1] != '(':
                    val2 = values.pop()
                    val1 = values.pop()
                    op = ops.pop()
                    values.append(self.applyOp(val1, val2, op))
                ops.pop() # pop opening brace
            else:
                while len(ops) != 0 and self.precedence(ops[-1]) >= self.precedence(tokens[i]):
                    val2 = values.pop()
                    val1 = values.pop()
                    op = ops.pop()
                    values.append(self.applyOp(val1, val2, op))
                ops.append(tokens[i]) # push current token
            i += 1

        while len(ops) != 0:
            val2 = values.pop()
            val1 = values.pop()
            op = ops.pop()
            values.append(self.applyOp(val1, val2, op))

        return values[-1]
        
    
    def precedence(self, op):
        if op in '+-':
            return 1
        elif op in '*/':
            return 2
        return 0
 
    def applyOp(self, a, b, op):
        if op == '+': 
            return a + b
        elif op == '-': 
            return a - b
        elif op == '*': 
            return a * b
        elif op == '/': 
            val = abs(a) // abs(b)
            sign = 1 if a // b >= 0 else -1
            return sign * val

772. Basic Calculator III - cocoder39/coco39_LC GitHub Wiki