Basic Calculator
Tags: leetcode, dsa, theabbie
Published: 2022-06-10 00:30:37

Given a string `s` representing a valid expression, implement a basic calculator to evaluate it, and return _the result of the evaluation_.

**Note:** You are **not** allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

**Input:** s = "1 + 1"
**Output:** 2

**Example 2:**

**Input:** s = " 2-1 + 2 "
**Output:** 3

**Example 3:**

**Input:** s = "(1+(4+5+2)-3)+(6+8)"
**Output:** 23

**Constraints:**

*   `1 <= s.length <= 3 * 105`
*   `s` consists of digits, `'+'`, `'-'`, `'('`, `')'`, and `' '`.
*   `s` represents a valid expression.
*   `'+'` is **not** used as a unary operation (i.e., `"+1"` and `"+(2 + 3)"` is invalid).
*   `'-'` could be used as a unary operation (i.e., `"-1"` and `"-(2 + 3)"` is valid).
*   There will be no two consecutive operators in the input.
*   Every number and running calculation will fit in a signed 32-bit integer.

**SOLUTION:**

    class Solution:
        def eval(self, a, op, b):
            if op == '+':
                return a + b
            elif op == '-':
                return a - b
            elif op == '/':
                return int(a / b)
            elif op == '*':
                return a * b
        
        def calculate(self, s: str) -> int:
            s += " "
            precedence = {
                '*': 1,
                '/': 1,
                '+': 0,
                '-': 0
            }
            brackets = {
                '(': 1,
                ')': -1
            }
            numstack = []
            opstack = []
            chunk = ""
            latestOpenBracket = True
            for c in s:
                if c == " " or c in precedence or c in brackets:
                    if len(chunk) > 0:
                        numstack.append(int(chunk))
                        chunk = ""
                    if c in brackets:
                        if brackets[c] == 1:
                            opstack.append('(')
                            latestOpenBracket = True
                        elif brackets[c] == -1:
                            latestOpenBracket = False
                            while opstack[-1] != '(':
                                currop = opstack.pop()
                                b = numstack.pop()
                                a = numstack.pop()
                                res = self.eval(a, currop, b)
                                numstack.append(res)
                            opstack.pop()
                    elif c in precedence:
                        if latestOpenBracket:
                            numstack.append(0)
                        while len(opstack) > 0 and precedence.get(opstack[-1], -1) >= precedence[c]:
                            currop = opstack.pop()
                            b = numstack.pop()
                            a = numstack.pop()
                            res = self.eval(a, currop, b)
                            numstack.append(res)
                        opstack.append(c)
                        latestOpenBracket = False
                else:
                    chunk += c
                    latestOpenBracket = False
            while len(opstack) > 0:
                currop = opstack.pop()
                b = numstack.pop()
                a = numstack.pop()
                res = self.eval(a, currop, b)
                numstack.append(res)
            return numstack[0]