Recursive Descent Parser Solution


  • 1
    A

    Here's a solution where we define a grammar using EBNF and implement a
    recursive descent parser.

    Evaluation Grammar (syntax might not be 100% correct))

    expression := number | "(" number ")" operator number | "("{expression}")"

    number := digit, {digit,}

    op := "+" | "-"

    inline bool isDigit(const char c){
        if('0' <= c && c <= '9')
            return true;
        else
            return false;
    }
    
    inline int evaluate(const int a, const int b, char op){
        if(op == '+')
            return a + b;
        else
            return a - b;
    }
    
    int i = 0;
    inline int getNum(const string& s){
        while(i < s.size() && s[i] == ' ')
            i++;
        //check if we went past then just return 0
        if(i >= s.size())
            return 0;
        //get number
        int num = 0;
        while(isDigit(s[i])){
            num *= 10;
            num += s[i] - '0';
            i++;
        }
        return num;
    }
    
    inline int expression(string& s){
        //ignore white space
        while(i < s.size() && s[i] == ' ')
                i++;
        int num1;
        if(s[i] == '('){
            i++;
            num1 = expression(s);
        }else{
            num1 = getNum(s);
        }
        while(i < s.size()){
            //ignore white space
            while(s[i] == ' ')
                i++;
            
            //get op
            if(s[i] == ')'){
                i++;
                break;
            }
            
            char op = s[i];
            i++;
            
            //ignore white space
            while(s[i] == ' ')
                i++;
                
            //get second number or return expression
            int num2 = 0;
            if(s[i] == '('){
                i++;
                num2 = expression(s);
            }else{
                num2 = getNum(s);
            }
            num1 = evaluate(num1, num2, op);
            
            //ignore white space
            while(s[i] == ' ')
                i++;
            
            //check for closing paren
            if(s[i] == ')'){
                i++;
                break;
            }
        }
        return num1;
    }
    
    int calculate(string s){
        //remove trailing white spaces
        int j = s.size()-1;
        while(j >= 0 && s[j] == ' '){
            if(s[j] == ' ')
                s.pop_back();
            else
                break;
            j--;
        }
        
        return expression(s);
    }

Log in to reply
 

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