C++ solution in 16 ms with comment


  • 0
    Y
    // The calculator can be implemented this way
    // because there is ONLY +/-. So one does not need
    // to consider priorities of operator -- just update the 
    // result whenever one meets a new operator
    
    // Another noticable point is that the sign of a number
    // is determined by two things: one is its sign, the other 
    // is a "background sign" --- the sign caused by brackets.
    // When you meet a '(', push the old backgound sign and 
    // update it. And when you meet a ')', restore the old 
    // background sign.
    
    class Solution {
    public:
        int calculate(string s) {
    
            int backgroundSign = 1;
            int prevSign = 1;
            int num = 0; // the number in the expression
            int ret = 0; // return value
            
            stack<int> bgsList; // store the background signs
            bgsList.push(backgroundSign);
            
            for (auto c : s) {
                switch (c) {
                    case '(': 
                       // update background sign
                        bgsList.push(backgroundSign);
                        backgroundSign *= prevSign;
                        prevSign = 1;
                        continue;
                    case ')':
                        // update the return value
                        ret = ret + prevSign*backgroundSign*num;
                        num = 0;
                        // restore the background sign
                        backgroundSign = bgsList.top();
                        bgsList.pop();
                        continue;
                    case '+':
                        // update return value
                        ret = ret + prevSign*backgroundSign*num;
                        // update prevSign
                        prevSign = 1;
                        num = 0;
                        continue;
                    case '-':
                        // update return value
                        ret = ret + prevSign*backgroundSign*num;
                        // update prevSign
                        prevSign = -1;
                        num = 0;
                        continue;
                    case ' ': 
                        // do nothing
                        continue;
                    default:
                        // update number
                        num *= 10;
                        num += c - '0';
                        continue;
                }
            }
            
            if (s[s.size()-1] == ')') return ret;
            else return ret + prevSign*backgroundSign*num;
        }
    };

  • 0
    K

    No consideration of priority, hmm...just enough to solve this one


Log in to reply
 

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