# Recursive Descent Parser Solution

• 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);
}``````

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