C++ Recursive Solution, One Pass, 13ms, beat 95%


  • 0
    X

    For example, given "1 - (2+3) + 4" expression, there are two level, first level is without parenthesis, second level is within the first parenthesis. One pass to calculate the final result of the expression by parsing reference of pos to calculate helper function.

    class Solution {
    public:
        int calculate(string s) {
            int pos = 0;
            return calculate(s, pos);
        }
        
    private:
        // Use pos to record the pos that we currently visit. 
        int calculate(string& s, int& pos) {
            int sum = 0, sign = 1;
            while (pos < s.size() && s[pos] != ')') {
                // Use recursive call to calculate next parenthesis
                if (s[pos] == '(') sum += sign * calculate(s, ++pos);
                else if (isdigit(s[pos])) {
                    // Use num to convert number from string to int
                    int num = s[pos]-'0';
                    while (isdigit(s[++pos])) {
                        num *= 10;
                        num += s[pos] - '0';
                    }
                    // Use sign to record the current sign
                    sum += sign*num;
                }
                else if (s[pos] == '+') {
                    sign = 1;
                    ++pos;
                }
                else if (s[pos] == '-') {
                    sign = -1;
                    ++pos;
                }
                else ++pos;
            }
            ++pos;
            return sum;
        }
    };
    

Log in to reply
 

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