Basic Calculator

---

Basic Calculator: 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 * 10^5
• 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.

---

Try this Problem on your own or check similar problems:

1. Basic Calculator II
2. Evaluate Reverse Polish Notation
3. Different Ways to Add Parentheses
4. Expression Add Operators

Solution:

Java

class Solution {
  public int calculate(String s) {
      return helper(s, 0)[0];
  }

  private int[] helper(String s, int start){
      int num = 0, lastNum = 0, result = 0;
      char operation = '+';

      int i = start;
      while(i < s.length()) {
          char c = s.charAt(i);
          if (Character.isDigit(c)) {
              num = (num * 10) + (c - '0');
          }
          if (!Character.isDigit(c) && !Character.isWhitespace(c) || i == s.length() - 1) {
              if (c == '('){
                  int[] eval = helper(s, i + 1);
                  num = eval[0];
                  i = eval[1];
              }

              if (operation == '+') {
                  result += lastNum;
                  lastNum = num;
              }
              else if (operation == '-') {
                  result += lastNum;
                  lastNum = -num;
              }

              if(c == ')' && start > 1){
                  return new int[]{result + lastNum, i};
              }

              operation = c;
              num = 0;
          }
          ++i;
      }

      return new int[]{ result + lastNum, i };
  }
}

JavaScript

var calculate = function (s) {
  return helper(s, 0)[0];
};

function helper(s, start) {
  let num = 0,
    lastNum = 0,
    result = 0;
  let operation = "+";

  let i = start;
  while (i < s.length) {
    let c = s.charAt(i);
    if (/\d/.test(c)) {
      num = num * 10 + (parseInt(c) - 0);
    }
    if (!/\d|\s/.test(c) || i === s.length - 1) {
      if (c === "(") {
        let eval = helper(s, i + 1);
        num = eval[0];
        i = eval[1];
      }

      if (operation === "+") {
        result += lastNum;
        lastNum = num;
      } else if (operation === "-") {
        result += lastNum;
        lastNum = -num;
      }

      if (c === ")" && start > 1) {
        return [result + lastNum, i];
      }

      operation = c;
      num = 0;
    }
    ++i;
  }

  return [result + lastNum, i];
}

Python

class Solution:
    def calculate(self, s: str) -> int:
        return self.helper(s, 0)[0]

    def helper(self, s: str, start: int) -> Tuple[int, int]:
        num, lastNum, result = 0, 0, 0
        operation = '+'

        i = start
        while i < len(s):
            c = s[i]
            if c.isdigit():
                num = num * 10 + int(c)
            if (not c.isdigit() and not c.isspace()) or i == len(s) - 1:
                if c == '(':
                    eval_result, eval_index = self.helper(s, i + 1)
                    num = eval_result
                    i = eval_index
                if operation == '+':
                    result += lastNum
                    lastNum = num
                elif operation == '-':
                    result += lastNum
                    lastNum = -num
                if c == ')' and start > 1:
                    return result + lastNum, i
                operation = c
                num = 0
            i += 1

        return result + lastNum, i

C++

class Solution {
public:
    int calculate(string s) {
        return helper(s, 0)[0];
    }

private:
    vector<int> helper(const string& s, int start) {
        int num = 0, lastNum = 0, result = 0;
        char operation = '+';

        int i = start;
        while (i < s.length()) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (!isdigit(c) && !isspace(c) || i == s.length() - 1) {
                if (c == '(') {
                    vector<int> eval = helper(s, i + 1);
                    num = eval[0];
                    i = eval[1];
                }
                if (operation == '+') {
                    result += lastNum;
                    lastNum = num;
                }
                else if (operation == '-') {
                    result += lastNum;
                    lastNum = -num;
                }
                if (c == ')' && start > 1) {
                    return {result + lastNum, i};
                }
                operation = c;
                num = 0;
            }
            ++i;
        }

        return {result + lastNum, i};
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

If we break down the expression into groups of expressions separated by ( and ) (e.g. 1 + (1+2), can be broken down to 1 and 1+2) we can utilize the solution we implemented in Basic Calculator II, but this time can have brackets inside brackets (1 + (1+2)) implying recursion, so we defined our helper function utilizing most of the implementation from Basic Calculator II. This time we only have to check if we encounter ( and then we recursively call the helper to evaluate the expression inside the brackets, we also have to store starting index for our recursion call. That's why instead of just returning the result of evaluation we return the last index (index of closing bracket )). When we encounter ) we check if we're in our first helper call (the root of recursion tree), we can easily check that if start > 1, and if it is we know we're inside recursion stack and we can return back the result and the last index. Otherwise, we're in the first/main call and wait until the loop has finished and only then return the result. Since we traverse the whole string s we have linear time complexity, also note now that we have recursion stack which will be proportional to the length of the input string s (number of brackets in s, it will always be smaller the whole length, but it can grow proportionally with string size) leading to linear space complexity.