224. Basic Calculator - cocoder39/coco39_LC GitHub Wiki

224. Basic Calculator

thinking process: 1. how to solve the problem if there is no parentheses 2. suppose we know how to solve step 1, then how to extend to solve the case there could be parenthesis -> stack

Notes 2022

  • variant of Basic CalculatorIII doesn't work because - could be used as unary operation
  • resetting res, num, sign to 0, 0, 1
  1. if ch == ' ': continue
  2. if digit: build up the number
  3. if (:
    • 3.1 push res and sign to stack
      • 3.1.1 one ( maps to 2 new elements being added to stack
    • 3.2 once the result within () is ready, new_res = res + sign * result
  4. if ):
    • 4.1 evaluate the result within () result = res + sign * num
    • 4.2 evaluate the effect of applying result to the previous evaluation result
      • 4.2.1 res = pre_res + pre_sign * result
      • 4.2.2 one ) maps to 2 pop operations from stack so at the end stack is supposed to be empty
      • 4.3 stack is empty at the end as ( and ) are pairing
      • no need to reset sign. if there is sign after ), sign will be reset properly
  5. if +/-:
    • 5.1 evaluate result and update sign and num
class Solution:
    def calculate(self, s: str) -> int:
        num_stack = []
        sign_stack = [] # can use same stack, as long as we follow pattern to insert (ie number then sign)
        res = 0 # res of current layer
        num = 0 # last built number in current layer
        sign = 1 # sign of last built number in current layer
        for ch in s:
            if ch.isdigit():
                num = num * 10 + ord(ch) - ord('0')
            elif ch == '+': # res sign num + 
                res += sign * num
                sign = 1
                num = 0
            elif ch == '-': # res sign num -
                res += sign * num
                sign = -1
                num = 0
            elif ch == '(': # res sign ( 
                num_stack.append(res)
                sign_stack.append(sign)
                res = 0
                num = 0
                sign = 1
            elif ch == ')': # res sign num )
                res += sign * num
                pre_res = num_stack.pop()
                pre_sign = sign_stack.pop()
                res = pre_res + pre_sign * res
                num = 0
                # no need to reset sign here
        
        # this happens only if num is outside of ()
        # if num is within (), it has been reset to 0
        return res + sign * num

==========================================================================

A op1 (B op2 C) => push A and op1 into stack, calculate result within parentheses, thus final result = result * op1 + A

int calculate(string s) {
        int res = 0;
        int num = 0;
        int sign = 1;
        stack<int> stk;
        for (int i = 0, len = s.length(); i < len; i++) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            } else if (s[i] == '+') { // end of preceding num
                res += sign * num;
                sign = 1;
                num = 0;
            } else if (s[i] == '-') { // end of preceding num
                res += sign * num;
                sign = -1;
                num = 0;
            } else if (s[i] == '(') { // at the start position or following an operator 
                stk.push(res);
                stk.push(sign);
                res = 0;
                sign = 1;
               // num = 0; // can be ignored
            } else if (s[i] == ')') { // follows a number
                res += sign * num; // result between a pair of parentheses
                num = 0;
                res *= stk.top();
                stk.pop();
                res += stk.top();
                stk.pop();
            }
        }
        res += sign * num;
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️