227. Basic Calculator II Medium

Given a string s which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:
Input: s = "3+2*2"
Output: 7

Example 2:
Input: s = " 3/2 "
Output: 1

Example 3:
Input: s = " 3+5 / 2 "
Output: 5

Approach

Input: A string expression s

Output: Return the calculated result of the expression (containing only non-negative integers and operators + - * /, with no parentheses)

This problem belongs to the Expression Evaluation Stack category.

We can achieve this by iterating through the string, combining a stack structure and operator precedence:

Steps:

1. Use a variable num to construct the current number (supports multi-digit numbers).
2. Use prev_op to record the previous operator, initially set to '+', which treats the first number as positive by default.
3. Use a stack stack to store the phased results of each step (to handle the precedence sequence of addition/subtraction and multiplication/division).
4. Iterate through the string:
   • If it's a digit, update num = num * 10 + int(c).
   • If an operator or the end of the string is encountered, process the current number based on prev_op:
     • '+': Push num to the stack;
     • '-': Push -num to the stack;
     • '*': Pop the top of the stack, multiply it by num, and push the result;
     • '/': Pop the top of the stack, divide it by num (note: truncate toward zero), and push the result.
   • Update prev_op = current operator, and reset num to 0.
5. Finally, return the sum of all elements in the stack as the final result.

Implementation

python

class Solution:
    def calculate(self, s: str) -> int:
        num = 0                  # Currently constructing number (possibly multi-digit)
        stack = []               # Stack, used to save the result of each segment
        prev_op = '+'            # Record previous operator, initially '+' (default first number is positive)

        # Iterate through every character of the string
        for i in range(len(s)):
            c = s[i]

            # If it's a digit character, accumulate into the current number
            if c.isdigit():
                num = num * 10 + int(c)

            # If an operator (+ - * /) is encountered, or reached the end of the string
            if (not c.isdigit() and c != ' ') or i == len(s) - 1:
                # Process current num according to the previous operator
                if prev_op == '+':
                    stack.append(num)  # Plus: directly push current number onto stack
                elif prev_op == '-':
                    stack.append(-num)  # Minus: turn current number to negative, then push onto stack
                elif prev_op == '*':
                    stack.append(stack.pop() * num)  # Multiply: pop top of stack, multiply by current number
                elif prev_op == '/':
                    # Divide: be careful to truncate toward zero (e.g., -3 / 2 should be -1, not -2)
                    stack.append(int(stack.pop() / num))

                prev_op = c  # Update the current operator to the one just encountered
                num = 0      # Reset current number, prepare to read the next number

        # The sum of all numbers in the stack is the final result
        return sum(stack)

javascript

/**
 * @param {string} s
 * @return {number}
 */
const calculate = function(s) {
    let num = 0;
    let stack = [];
    let prev_op = '+';

    for (let i in s) {
        const c = s[i];

        if (/[0-9]/.test(c)) num = num * 10 + Number(c);

        if (!/[0-9]/.test(c) && c !== ' ' || i == s.length - 1) {
            if (prev_op == '+') stack.push(num); 
            if (prev_op == '-') stack.push(-num);
            if (prev_op == '*') stack.push(stack.pop() * num);
            if (prev_op == '/') stack.push(parseInt(stack.pop() / num));

            num = 0;
            prev_op = c;
        }
    }

    return stack.reduce((acc, curr) => acc + curr, 0);
};

Complexity Analysis

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

Links

227. Basic Calculator II (English)

227. 基本计算器 II (Chinese)