Neat C++ solution with explanation


  • 0
    C

    I keep a stack of operators and 3 numbers: num to store current number if we encounter, prev is to store the previous number (the one on the left side of * or /), and res is the result.

    A little trick I did first is to add a space to the end of the string so that after we finish the last number of the string, we can update the result right away. Otherwise we have to update result the last time after we are done with the loop. See more comments in the code.

    class Solution {
    public:
        int calculate(string s) {
            s.push_back(' '); // add a space at the end
            stack<char> ops;
            int num = 0, res = 0, prev = 0;
            ops.push('+');
            for (int i = 0; i < s.size(); i++){
                // if what we encounter is digit: update num
                if (s[i] >= '0' && s[i] <= '9') num = num*10 + s[i] - '0';
                else if (s[i] != ' ' || i == s.size()-1) { //else if we reach an operator or at the end
                    if (ops.top() == '*' || ops.top() == '/') { //First process the previous operator stored in ops if it was * or /
                        num = ops.top() == '*' ? prev * num : prev/num;
                        ops.pop();
                    } // Now we are sure that the top of ops is + or -
                    // if what we encounter is + or -, or this is the last element then update res, remove the last operator 
                    if (s[i] == '+' || s[i] == '-' || i == s.size()-1) {
                        res = ops.top() == '+' ? res + num : res - num;
                        ops.pop();
                    }
                    else if (s[i] == '*' || s[i] == '/') prev = num; // Just set the prev to num
                    ops.push(s[i]); // update ops stack and num what ever the operator we encounter is
                    num = 0;
                }
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.