how to use recursive descent algorithm to compute an arithmetical expression?

tony_ming

I want to use recursive descent algorithm to compute an arithmetical expression, but I can't get the right value,so please tell me how to write the code here is my grammar

E→E+T|E-T|T
T→T*F| T/F|F
F→(E)|i

the following is my code

#include
#include
using namespace std;
int pos = 0;
string str = "1+2*3-4";
double E();
double T();
double F();

int main() {
double v = E();
printf("%f", v);
getchar();
return 0;
}

double E() {
double v = 0;
char c = str.at(pos);
if (c == '+') {
pos++;
v = E() + T();
}
else if (c == '-') {
pos++;
v = E() - T();
}
else {
pos++;
v = T();
}
return v;
}

double T() {
double v = 0;
char c = str.at(pos);
if (c == '*') {
pos++;
v = T() * F();
}
else if (c == '/') {
pos++;
v = T() / F();
}
else {
pos++;
v = F();
}
return v;
}

double F() {
char c = str.at(pos);
if (c == '(') {
pos++;
double v = E();
c = str.at(pos);
if (c == ')') {
pos++;
return v;
}
}
else {
string s = "";
while (true) {
c = str.at(pos);
if (c >= '0' && c <= '9') {
s += c;
pos++;
}
else {
break;
}
}

	return atoi(s.c\_str());
}
return 0;

}

Lost User

You are not checking for '-':

if (c == '+') {
	pos++;
	v = E() + T();
}
else if (c == '+') { // already tested for '+'
	pos++;
	v = E() - T();
}

You are also incrementing the value of pos if the operator is not one of the two you test for. So when you call the next function it will see the next character rather than the current one. You could improve this by replacing all these functions with a single switch block.

Stefan_Lang

The logic in your parse functions is flawed: it first looks for the operator, and only then looks for the arguments. This would only work for an expression like "+ 1 2" rather than "1 + 2". You have to change your code to first split it into tokens and then check the second (and maybe following) token(s) of the remaining part of your expression string for operators, before passing the first token(s) and the rest of the tokens (after the operator) on to the next recursion step. P.S.: It is always a bad idea to use global variables in a program. But it is especially devastating when using recursive functions! I don't see any reasonable way to implement E(), T() and F() without passing the part of the string that needs to be analyzed. The advantage is that you don't need to split the whole string into tokens up front as I suggested at first. Instead each function just searches its part of the string for the operators that it can interpret, extract the arguments of that operator accordingly, and pass those into further recursive calls. P.P.S.: example for function E():

double E (const std::string& str) {
size_t op_pos = str.find_first_of("+-", 1); // search for '+' or '-' starting at the second character of the string
if (op_pos == std::string::npos) { // not found
return T(str);
}

std::string first_operand = str.substr(0, op_pos);
std::string second_operand = str.substr(op_pos+1);
return (str.at(op_pos) == '+')
? E(first_operand) + T(second_operand)
: E(first_operand) - T(second_operand)
}

GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)

David Crow

Have you seen this?

"One man's wage rise is another man's price increase." - Harold Wilson

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles

CPallini

You have first to fix your grammar, removing left recursion. See, for instance: CS 3721 Programming Languages Recursive Descent Parsing.