C++ recursive clean code, inspired by "miniparser" recursive solution. Recursive solution template for string parse with brackets.


  • 0
    C

    There are many iterative solutions around, but not so for recursion.
    I was inspired by the recursive solution of mini parser https://discuss.leetcode.com/topic/94538/c-clean-recursive-code
    So I wrote the following recursive solution.

        int parse(string& s, int& i) {
            for(; i < s.length() && s[i] == ' '; i++) {}
            if(i == s.length()) return 0;
            int sign = 1;
            if(s[i] == '+') i++;
            else if(s[i] == '-') {
                sign = -1; i++;
            }
            
            if(s[i] == '(') {
                i++;
                int ans = 0;
                for(; i < s.length() && s[i] == ' '; i++) {}
                while(s[i] != ')') {
                    ans += parse(s, i);
                }    
                i++;
                return sign*ans + parse(s, i);
            }
            else {
                int num = 0;
                while(i < s.length() && isdigit(s[i])) num = num * 10 + s[i++] - '0';
                return sign * num;
            }
        }
        int calculate(string s) {
            int i = 0;
            s = "(" + s + ")";
            return parse(s, i);
        }
    

    A template for this kind of string parse problem can be generalized:

        int parse(string& s, int& i) {
            // may need to skip space or undesired stuff. 
            if(s[i] == '(') {
                // skip space or other stuff if necessary 
                auto ans = ; // ans is a data structure depending on the problem. 
                while(s[i] != ')') {
                    ans += or append or ... parse(s, i);
                    // skip space or other stuff if necessary 
                }
                i++;
                return ans (optional + parse()) // depends on problem, keep recursion or not)
            }
            else {
                int num = 0;
                while(i < s.length() && isdigit(s[i])) num = num * 10 + s[i++] - '0';
                return (optional sign*) num;
            }
        }
        int driver(string s) {
            int i = 0;
            // To help parse, add extra prefix / suffix to s if necessary.
            return parse(s, i);
        }
    

    I also used this template for the following problems:
    https://discuss.leetcode.com/topic/95971/c-clean-recursive-solution-using-template


Log in to reply
 

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