Code Implementation

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(' ', '')
        stack = []
        num = 0
        sign = '+'
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in '+-*/' or i == len(s) - 1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                elif sign == '/':
                    prev = stack.pop()
                    # Truncate towards zero
                    stack.append(int(prev / num))
                sign = c
                num = 0
        return sum(stack)
      

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        long num = 0;
        char sign = '+';
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!isdigit(c) && c != ' ') || i == n - 1) {
                if (sign == '+') stk.push(num);
                else if (sign == '-') stk.push(-num);
                else if (sign == '*') {
                    int t = stk.top(); stk.pop();
                    stk.push(t * num);
                }
                else if (sign == '/') {
                    int t = stk.top(); stk.pop();
                    stk.push(t / num);
                }
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        while (!stk.empty()) {
            res += stk.top(); stk.pop();
        }
        return res;
    }
};
      

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

var calculate = function(s) {
    s = s.replace(/ /g, '');
    let stack = [];
    let num = 0;
    let sign = '+';
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (!isNaN(Number(c))) {
            num = num * 10 + Number(c);
        }
        if (isNaN(Number(c)) || i === s.length - 1) {
            if (sign === '+') stack.push(num);
            else if (sign === '-') stack.push(-num);
            else if (sign === '*') stack.push(stack.pop() * num);
            else if (sign === '/') stack.push(parseInt(stack.pop() / num));
            sign = c;
            num = 0;
        }
    }
    return stack.reduce((a, b) => a + b, 0);
};
      

Problem Description

You are given a string s that represents a basic mathematical expression containing non-negative integers and the operators '+', '-', '*', and '/'. The expression does not contain any parentheses. The division operator should truncate toward zero.

• Only spaces, digits, and the operators listed above are present in s.
• Each integer may have multiple digits.
• You must evaluate the expression and return the result as an integer.
• There is exactly one valid answer for each input string.

Example: s = "3+2*2" should return 7.

Thought Process

At first glance, it might seem reasonable to process the string from left to right, applying each operation as you encounter it. However, the presence of multiplication and division (which have higher precedence than addition and subtraction) complicates things. For example, in "3+2*2", you must calculate 2*2 before adding 3.

A naive approach would be to parse and evaluate the expression as you go, but this fails when operator precedence is not respected. To solve this, we need a way to process multiplication and division immediately when we see them, while postponing addition and subtraction until the end. This is similar to how a calculator works: it keeps track of the last operation and applies it as soon as possible.

Solution Approach

We can solve this problem efficiently by using a stack to keep track of numbers and the last seen operator. Here's a step-by-step breakdown:

1. Initialize an empty stack, a variable num to build the current number, and a variable sign to remember the last operator (start with '+').
2. Iterate through each character c in the string s:
• If c is a digit, build the current number (num = num * 10 + int(c)).
• If c is an operator or it's the last character:
  • If the previous sign is '+', push num to the stack.
  • If '-', push -num to the stack.
  • If '*', pop the top of the stack, multiply by num, and push the result.
  • If '/', pop the top, divide by num (truncate toward zero), and push the result.
• Update sign to the current operator and reset num to 0.
3. After processing the entire string, sum up all numbers in the stack to get the result.

This approach ensures that multiplication and division are handled immediately, while addition and subtraction are summed at the end, preserving the correct precedence.

Example Walkthrough

Let's walk through the input s = "3+2*2":

1. Start: stack = [], num = 0, sign = '+' .
2. Read '3': num = 3.
3. Read '+': Previous sign is '+', so push 3 to stack. stack = [3]. Set sign = '+' , num = 0.
4. Read '2': num = 2.
5. Read '*': Previous sign is '+', so push 2 to stack. stack = [3, 2]. Set sign = '*', num = 0.
6. Read '2': num = 2. End of string.
7. End: Previous sign is '*', pop 2 from stack, multiply by 2, push 4. stack = [3, 4].
8. Sum stack: 3 + 4 = 7.

The answer is 7, as expected.

Time and Space Complexity

Brute-force approach: Parsing and evaluating the expression with full operator precedence (using two stacks or converting to postfix notation) would still be O(n), but with more overhead for managing stacks or lists.

Optimized approach (stack-based as above):

• Time Complexity: O(n), where n is the length of the string s. Each character is processed once.
• Space Complexity: O(n) in the worst case, for the stack (if all numbers are added or subtracted).

Summary

The key insight is to process multiplication and division immediately using a stack, while deferring addition and subtraction until the end. This approach efficiently respects operator precedence without the need for complex parsing or conversion to postfix notation. By iterating through the string and using a stack, we ensure a clean O(n) solution that is both simple and effective.