Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/224.html

 224	Basic Calculator

 Implement a basic calculator to evaluate a simple expression string.

 The expression string may contain
    open ( and closing parentheses ),
    the plus +
    or minus sign -,
    non-negative integers and
    empty spaces .

 Example 1:

 Input: "1 + 1"
 Output: 2

 Example 2:

 Input: " 2-1 + 2 "
 Output: 3

 Example 3:

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

 Note:
     You may assume that the given expression is always valid.
     Do not use the eval built-in library function.

Algorithm

The title restricts the expressions with only plus and minus signs, numbers, parentheses and spaces, and there is no multiplication and division, so there is no priority of calculation.

A stack is needed to assist the calculation, and a variable sign is used to represent the current symbol.

We traverse the given string s,

  • If you encounter a number, because it may be a multi-digit number, we need to use a while loop to read all the subsequent numbers in, and then use sign*num to update the result res;
  • If a plus sign is encountered, sign is assigned to 1, and if a minus sign is encountered, it is assigned to -1;
  • If a left parenthesis is encountered, push the current result res and sign onto the stack, reset res to 0 and reset to 1;
  • If the closing parenthesis is encountered, the result res is multiplied by the symbol on the top of the stack, the top element of the stack is popped, and the result is res plus the number on the top of the stack, and the top element of the stack is popped.

Code

Java

  • import java.util.Stack;

public class Basic_Calculator {

    class Solution {
        public int calculate(String s) {
            int res = 0;
            int num = 0;
            int sign = 1;
            int n = s.length();

            Stack<Integer> sk = new Stack<>();

            for (int i = 0; i < n; ++i) {
                char c = s.charAt(i);
                if (c >= '0') {
                    num = 10 * num + (c - '0');
                } else if (c == '+' || c == '-') {
                    res += sign * num; // possible overflow, eg. -1 * Integer.MIN_VALUE
                    num = 0;
                    sign = (c == '+') ? 1 : -1;
                } else if (c == '(') {
                    sk.push(res); // not c-'0'
                    sk.push(sign);
                    res = 0;
                    sign = 1;
                    num = 0; // this line can be removed, here for clarity, since it's set to 0 when hitting operator +/-
                } else if (c == ')') {
                    res += sign * num;
                    num = 0;
                    res *= sk.peek(); sk.pop(); // sign @note: can be replaced by just `-1*val`
                    res += sk.peek(); sk.pop(); // then previous result
                }
            }
            res += sign * num; // @note: final check, if no ')' to trigger stack pop stuff
            return res;
        }

    }
}

  • // OJ: https://leetcode.com/problems/basic-calculator/
// Time: O(N)
// Space: O(N)
class Solution {
    vector<string> tokenize(string &s) {
        vector<string> ans;
        for (int i = 0, N = s.size(); i < N; ) {
            while (i < N && s[i] == ' ') ++i;
            if (i >= N) break;
            if (isdigit(s[i])) {
                int j = i;
                while (i < N && isdigit(s[i])) ++i;
                ans.push_back(s.substr(j, i - j));
            } else ans.push_back(s.substr(i++, 1));
        }
        return ans;
    }
    vector<string> toRpn(vector<string> tokens) {
        vector<string> ans;
        stack<string> ops;
        for (auto &s : tokens) {
            switch (s[0]) {
                case '(': ops.push(s); break;
                case ')':
                    while (ops.top() != "(") {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.pop();
                    break;
                case '+': 
                case '-':
                    if (ops.size() && (ops.top() == "+" || ops.top() == "-")) {
                        ans.push_back(ops.top());
                        ops.pop();
                    }
                    ops.push(s);
                    break;
                default: ans.push_back(s); break;
            }
        }
        while (ops.size()) {
            ans.push_back(ops.top());
            ops.pop();
        }
        return ans;
    }
    int calc(vector<string> rpn) {
        stack<int> s;
        for (auto &t : rpn) {
            switch (t[0]) {
                case '+':
                case '-': {
                    int b = s.top();
                    s.pop();
                    s.top() += t == "+" ? b : -b;
                    break;
                }
                default: s.push(stoi(t)); break;
            }
        }
        return s.top();
    }
public:
    int calculate(string s) {
        return calc(toRpn(tokenize(s)));
    }
};

  • class Solution:
  def calculate(self, s: str) -> int:
    ans = 0
    num = 0
    sign = 1
    stack = [sign]  # stack[-1]: current env's sign

    for c in s:
      if c.isdigit():
        num = num * 10 + (ord(c) - ord('0'))
      elif c == '(':
        stack.append(sign)
      elif c == ')':
        stack.pop()
      elif c == '+' or c == '-':
        ans += sign * num
        sign = (1 if c == '+' else -1) * stack[-1] # after all + or -, the sign for current num
        num = 0

    return ans + sign * num

#############

class Solution(object):
  def calculate(self, s):
    """
    :type s: str
    :rtype: int
    """
    s = "(" + s + ")"
    stack = []
    _stack = []
    i = 0
    while i < len(s):
      if s[i] == " ":
        i += 1
      elif s[i] == "(":
        _stack.append(len(stack))
        i += 1
      elif s[i] == ")":
        start = _stack.pop()
        j = start
        a = stack[j]
        while j + 2 < len(stack):
          ops = stack[j + 1]
          if ops == "+":
            a = a + stack[j + 2]
          elif ops == "-":
            a = a - stack[j + 2]
          else:
            return "invalid"
          j += 2
        k = len(stack) - start
        while k > 0:
          stack.pop()
          k -= 1
        stack.append(a)
        i += 1
      elif s[i] in "+-":
        stack.append(s[i])
        i += 1
      else:
        start = i
        while i < len(s) and s[i] not in "-+() ":
          i += 1
        num = int(s[start:i])
        stack.append(num)
    return stack[0]

All Problems

All Solutions