{x}
blog image

Basic Calculator III

Solution Explanation for Basic Calculator III

This problem requires evaluating a mathematical expression string containing integers, basic arithmetic operators (+, -, *, /), and parentheses. The solution uses a two-stack approach (one for operators and one for operands) to handle the order of operations, respecting parentheses and operator precedence.

Approach

The algorithm iterates through the input string s. Numbers are directly pushed onto the num stack. Operators are handled based on their precedence and the presence of parentheses:

  1. Higher Precedence: If the current operator has higher precedence than the top of the op stack (or the stack is empty), it's pushed onto the op stack.

  2. Lower or Equal Precedence: If the current operator has lower or equal precedence, operators are popped from the op stack and corresponding operands from the num stack, calculations are performed, and the result is pushed back onto the num stack until the precedence condition is satisfied or the stack is empty.

  3. Parentheses: Opening parentheses ( are pushed onto the op stack. Closing parentheses ) trigger the evaluation of the expression within the parentheses. Operators are popped and calculations are performed until an opening parenthesis is encountered, at which point the parenthesis is also popped.

  4. Multi-digit Numbers: The code handles multi-digit numbers by accumulating digits until a non-digit character is encountered.

  5. Unary Minus/Plus: The code addresses unary minus/plus (like -5 or +5) by handling cases where the stack is empty and the current character is a - or +.

After processing the entire string, any remaining operators and operands on the stacks are processed to yield the final result.

Code (C++)

class Solution {
public:
    int operate(int b, char ch, int a) {
        switch (ch) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
            default: return 0;
        }
    }
 
    int calculate(string s) {
        int preority[250];
        preority['+'] = 1; preority['-'] = 1;
        preority['*'] = 2; preority['/'] = 2;
        preority['('] = 0; preority[')'] = 0;
 
        stack<char> op;
        stack<int> num;
        int stringsize = s.size();
        int i = 0;
        char ch;
 
        for (; i < stringsize; i++) {
            ch = s[i];
            if (ch == ' ') continue;
            if (ch >= '0' && ch <= '9') {
                int realnum = ch - '0';
                while (s[i + 1] >= '0' && s[i + 1] <= '9') {
                    i++;
                    realnum *= 10;
                    realnum += s[i] - '0';
                }
                num.push(realnum);
            } else {
                if (op.empty() || ch == '(' || preority[ch] > preority[op.top()]) {
                    if (num.empty() && (ch == '-' || ch == '+')) num.push(0);
                    op.push(ch);
                    if (ch == '(') {
                        int j = i;
                        while (j + 1 < stringsize) {
                            if (s[j + 1] == '-' || s[j + 1] == '+') num.push(0);
                            if (s[j + 1] != ' ') break;
                            j++;
                        }
                    }
                } else if (ch == ')') {
                    char ch2 = ')';
                    ch2 = op.top();
                    op.pop();
                    while (ch2 != '(') {
                        int a = num.top(); num.pop();
                        int b = num.top(); num.pop();
                        num.push(operate(a, ch2, b));
                        ch2 = op.top();
                        op.pop();
                    }
                } else if (preority[ch] <= preority[op.top()]) {
                    char ch2;
                    ch2 = op.top();
                    while (!op.empty() && preority[ch] <= preority[op.top()] && ch2 != '(') {
                        op.pop();
                        int a = num.top(); num.pop();
                        int b = num.top(); num.pop();
                        num.push(operate(a, ch2, b));
                        if (!op.empty()) ch2 = op.top(); else break;
                    }
                    op.push(ch);
                }
            }
        }
        while (!op.empty()) {
            ch = op.top();
            op.pop();
            int a = num.top(); num.pop();
            int b = num.top(); num.pop();
            num.push(operate(a, ch, b));
        }
        return num.top();
    }
};

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input string. Each character is processed at most a constant number of times.

  • Space Complexity: O(n) in the worst case, due to the stack. The maximum size of the stacks can be proportional to the length of the input string (e.g., deeply nested parentheses). In practice, it's likely to be much less than n.

The provided C++ code implements this approach effectively. The other languages (Python, Java, Go) would use similar logic with their respective stack implementations. The key is the careful handling of operator precedence and parentheses using the stack-based approach.