Recursive C++ solution, easy to understand.


  • 0
    S
    class Solution {
        
        //assumes that there is always something in s[start], returns parsed value and the position after the end of term 
        int parseTerm(string& s, int start, int& end){
            if(s[start]=='(')
                return parseExpression(s, start+1, end);
            else{
                int value=0;
                for (end=start;end<s.size();++end){
                    char c=s[end]; 
                    if(!isdigit(c)) break;
                    value*=10;
                    value+=c-'0';
                }
                return value;
            }
            
        }
        //end is set to the character following the expression, i.e. after ')'
        int parseExpression(string& s, int start, int& end){
            int total=0;
            if(start==s.size()) return total;
            else if(s[start] == ')') {
                end=start+1;
                return total;
            }
            total=parseTerm(s,start,end);
            while(end!=s.size()& s[end]!=')'){
                bool op=s[end]=='+';
                start=end+1;
                int term=parseTerm(s, start, end);
                if(op)
                    total+=term;
                else
                    total-=term;
            }
            if(s[end]==')') end++;
            return total;
            }
            
        void compress(string& s){
            int begin=0;
            for(int i=0;i<s.size();i++){
                if(s[i]!=' ') s[begin++]=s[i];
            }
            s.resize(begin);
        }
            
        
    public:
        int calculate(string s) {
            int end=0;
            compress(s);
            return parseExpression(s, 0, end);
            
        }
    };

Log in to reply
 

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