A 20ms Recursive C++ Solution with comments


  • 0
    Y

    I use recursive method to calculate result in the parentheses

    class Solution {
    public:
        int calculate(string s) {
            if(!s.length()) return 0;
            vector<int> ans;
            ans = cal(s,0);
            return ans[0];
        }
        
        /* Noted here the input argument str must set to const string or will get "Memory Limit Exceeded" result in OJ*/
        vector<int> cal(const string str, int stpos) {
            long int subsum = 0;
            vector<int> ans;
            int i = 0;
            int currsign = 1;  // Initial current sign as a plus sign.
            for(i = stpos; i < str.length(); i++) {
                char ch = str[i];
                switch(ch) {
                    case ' ': {break;}
                    case '+': {currsign = 1; break;}
                    case '-': {currsign = -1; break;}
                    case '(': {
                        // if a left parenthesis is founded, recursively call "cal" function to calculate the result in the parentheses
                        vector<int> ans1;
                        ans1 = cal(str,i + 1); // input the string and the start position, which is next position of the left parenthesis, into "cal" function
                        subsum += ans1[0]*currsign; // output vector contain the result and the position of right parenthesis
                        i = ans1[1]; // set current index to the outut index of right parenthesis
                        break;
                    }
                    case ')': {
                        vector<int> ans2;
                        ans2.push_back(subsum);
                        ans2.push_back(i);
                        return ans2; break;   // if a rigt parenthesis is founded, the return the current result
                    }
                    default: {
                        if((ch >= '0')&&(ch <= '9')) {
                            // if a digit is founded, check the number length using while
                            int j = i;
                            long int currnum = ch - '0';
                            while((str[j + 1] >= '0')&&(str[j + 1] <= '9')) {
                                //if next char is also a digit, then original number multiply by 10 and add that digit
                                currnum = currnum * 10 + str[j + 1] - '0';
                                j++;
                            }
                            // current result equals to the previous result plus current number(with sign)
                            subsum += currnum * currsign;
                            i = j; // set the current index to the index of the last consecutive digit char
                        }
                    }
                }
            }
            // after analysis of all the input char, return the result 
            ans.push_back(subsum);
            ans.push_back(i);
            return ans;
        }
    };

Log in to reply
 

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