227. Basic Calculator II

Description

Given a string s representing a basic mathematical expression containing non-negative integers and operators (+, -, *, /), implement a function to evaluate the expression and return its value. The expression is assumed to be well-formed, meaning it contains no parentheses and follows standard precedence rules for operators (* and / have higher precedence than + and -).

Intuition

The problem can be solved by iterating through the string and processing each character. The idea is to maintain a running total using a stack to handle the operations according to their precedence. By pushing intermediate results onto the stack, we can ensure that multiplication and division operations are handled before addition and subtraction, without explicitly handling operator precedence.

Approach

1. Initialization: Start by initializing a stack to hold intermediate results, a variable num to build the current number as you iterate through the string, and a variable prev_operator to keep track of the last operator encountered.
2. Iteration: Loop through the string, character by character: - If the character is a digit, update num by appending the digit to the current number. - If the character is an operator or you've reached the end of the string, process the num according to the previous operator (+, -, *, /): - For +, push num onto the stack. - For -, push -num onto the stack. - For *, pop the last number from the stack, multiply it by num, and push the result back onto the stack. - For /, pop the last number from the stack, divide it by num, and push the truncated result back onto the stack. - Reset num to 0 and update prev_operator to the current character.
3. Final Calculation: After the loop, sum all the numbers in the stack. This sum represents the final result of the expression.

Complexity

Time Complexity:

O(n), where n is the length of the string s. The algorithm processes each character in the string once, performing constant-time operations for each character.

Space Complexity:

O(n), where n is the number of elements pushed onto the stack. In the worst case, every number and intermediate result could be pushed onto the stack, leading to linear space usage.

Code

C++

class Solution {
public:
    int calculate(string s) {
        stack st;
        int num = 0;
        char prevOperator = '+';

        for (int i = 0; i <= s.length(); i++) {
            char ch = (i < s.length()) ? s[i] : '\0';

            if (isdigit(ch)) {
                num = num * 10 + (ch - '0');
            }

            if ((!isdigit(ch) && ch != ' ') || i == s.length()) {
                if (prevOperator == '+') st.push(num);
                if (prevOperator == '-') st.push(-num);
                if (prevOperator == '*') {
                    int temp = st.top() * num;
                    st.pop();
                    st.push(temp);
                }
                if (prevOperator == '/') {
                    int temp = st.top() / num;
                    st.pop();
                    st.push(temp);
                }

                prevOperator = ch;
                num = 0;
            }
        }

        int result = 0;
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }

        return result;
    }
};

// Usage Example
// int main() {
//     Solution sol;
//     string expression = "3+2*2";
//     int result = sol.calculate(expression);
//     cout << "Result: " << result << endl; // Output: 7
//     return 0;
// }

Python

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        prev_operator = '+'
        
        for i in range(len(s) + 1):
            ch = s[i] if i < len(s) else '\0'
            
            if ch.isdigit():
                num = num * 10 + int(ch)
            
            if not ch.isdigit() and ch != ' ' or i == len(s):
                if prev_operator == '+':
                    stack.append(num)
                if prev_operator == '-':
                    stack.append(-num)
                if prev_operator == '*':
                    stack.append(stack.pop() * num)
                if prev_operator == '/':
                    stack.append(int(stack.pop() / num))
                
                prev_operator = ch
                num = 0
        
        return sum(stack)

Java

class Solution {
    public int calculate(String s) {
        Stack stack = new Stack<>();
        int num = 0;
        char prevOperator = '+';

        for (int i = 0; i <= s.length(); i++) {
            char ch = (i < s.length()) ? s.charAt(i) : '\0';

            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }

            if (!Character.isDigit(ch) && ch != ' ' || i == s.length()) {
                if (prevOperator == '+') stack.push(num);
                if (prevOperator == '-') stack.push(-num);
                if (prevOperator == '*') stack.push(stack.pop() * num);
                if (prevOperator == '/') stack.push(stack.pop() / num);

                prevOperator = ch;
                num = 0;
            }
        }

        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }

        return result;
    }
}

JavaScript

var calculate = function (s) {
    
    let num = '';
    let prevOperator = '+';
    const stack = [];

    for (let i = 0; i <= s.length; i++) {
        const ch = s[i];

        if (ch >= '0' && ch <= '9') {
            num += ch;
        }

        if ((ch < '0' || ch > '9') && ch !== ' ' || i === s.length) {
            if (prevOperator === '+') stack.push(Number(num));
            if (prevOperator === '-') stack.push(-Number(num));
            if (prevOperator === '*') stack.push(stack.pop() * Number(num));
            if (prevOperator === '/') stack.push(Math.trunc(stack.pop() / Number(num)));

            prevOperator = ch;
            num = '';
        }
    }

    return stack.reduce((total, cur) => total + cur, 0);
};