224. Basic Calculator

At a Glance

Topic: Math
Pattern: Analyze Pattern
Difficulty: Hard
LeetCode: 224

Problem Statement

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, &#39;+&#39;, &#39;-&#39;, &#39;(&#39;, &#39;)&#39;, and &#39; &#39;.
s represents a valid expression.
&#39;+&#39; is not used as a unary operation (i.e., &quot;+1&quot; and &quot;+(2 + 3)&quot; is invalid).
&#39;-&#39; could be used as a unary operation (i.e., &quot;-1&quot; and &quot;-(2 + 3)&quot; 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.

Approach & Solution Steps

Use a stack to keep track of the result and signs before parentheses. Accumulate numbers and apply the current sign.

Optimal JS Solution

function calculate(s) {
  let stack = [];
  let res = 0;
  let num = 0;
  let sign = 1;
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char >= '0' && char <= '9') {
      num = num * 10 + Number(char);
    } else if (char === '+' || char === '-') {
      res += sign * num;
      num = 0;
      sign = char === '+' ? 1 : -1;
    } else if (char === '(') {
      stack.push(res);
      stack.push(sign);
      res = 0;
      sign = 1;
    } else if (char === ')') {
      res += sign * num;
      num = 0;
      res *= stack.pop(); // sign
      res += stack.pop(); // result before parenthesis
    }
  }
  res += sign * num;
  return res;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.