Basic Calculator II

medium string stack math

Problem

Evaluate an arithmetic expression of non-negative integers and the operators +, −, ×, ÷ (integer division truncates toward zero). No parentheses. Spaces may appear anywhere.

Inputs = "3+2*2"

Output7

Keep a stack of additive terms; on ×/÷ pop the top and push the combined value to respect precedence.

expression

def calculate(s):
    stack = []
    num, op = 0, '+'
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        if (not c.isdigit() and c != ' ') or i == len(s) - 1:
            if op == '+': stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop() * num)
            elif op == '/': stack.append(int(stack.pop() / num))
            num, op = 0, c
    return sum(stack)

function calculate(s) {
  const stack = [];
  let num = 0, op = '+';
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c >= '0' && c <= '9') num = num * 10 + (c.charCodeAt(0) - 48);
    if ((c !== ' ' && (c < '0' || c > '9')) || i === s.length - 1) {
      if (op === '+') stack.push(num);
      else if (op === '-') stack.push(-num);
      else if (op === '*') stack.push(stack.pop() * num);
      else if (op === '/') stack.push(Math.trunc(stack.pop() / num));
      num = 0; op = c;
    }
  }
  return stack.reduce((a, b) => a + b, 0);
}

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0; char op = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else stack.push(stack.pop() / num);
                num = 0; op = c;
            }
        }
        int sum = 0; for (int v : stack) sum += v; return sum;
    }
}

class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        int num = 0; char op = '+';
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) num = num * 10 + (c - '0');
            if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {
                if (op == '+') st.push_back(num);
                else if (op == '-') st.push_back(-num);
                else if (op == '*') { int t = st.back(); st.pop_back(); st.push_back(t * num); }
                else { int t = st.back(); st.pop_back(); st.push_back(t / num); }
                num = 0; op = c;
            }
        }
        int sum = 0; for (int v : st) sum += v; return sum;
    }
};

Explanation

The tricky part of this expression is operator precedence: * and / must happen before + and -. The neat trick is to keep a stack of additive terms and fold multiplication and division into the top of the stack immediately, so at the end you just add everything up.

We scan the string building up a number num digit by digit, and we remember the previous operator op (starting as '+'). When we hit a new operator (or the end of the string), we apply op to the number we just finished reading.

If op was + we push num; if - we push -num. But if op was * or /, we pop the top of the stack and push the combined result, applying the high-precedence math right away.

Example: "3+2*2". Read 3, op is + → push 3 → [3]. Read 2 at *, op is + → push 2 → [3,2]. Read 2 at end, op is * → pop 2, push 2*2=4 → [3,4]. Sum = 7.

Because each multiply/divide collapses into the top term, the remaining stack only ever holds values to be added, and the final answer is their sum.

Time: O(n) Space: O(n)