Odtnhj

Here's an algorithm for evaluating an arithmetic expression using recursion:

• Find operand1


• t1 = Eval(operand1)


• Find operand2


• t2 = Eval(operand2)


• Apply operator on t1 and t2

Assumptions:

• each operand is between two operators



• there are only binary operations




• for each operation, there are parentheses (including outermost parentheses)

Input:

• array of tokens representing an arithmetic expression




• num_tokens is the number of tokens

Sample array of tokens: "(", "9", "+", "(", "50", "-", "25", ")", ")"

I tried to implement the algorithm but my program doesn't run (exit status -1 is the only message I get). Why is that happening?

int apply(char op, int a, int b) 
 if (op == '+')
 printf("%d %c %dn", a,op,b);
 return a + b;
 
 else if (op == '-')
 printf("%d %c %dn", a,op,b);
 return a - b;
 
 else if(op == '/')
 printf("%d %c %dn", a,op,b);
 return a / b;
 
 else if(op == '*')
 printf("%d %c %dn", a,op,b);
 return a * b;
 
 

int eval_tokens(char** expression, int num_tokens)

 // implement me
 int index;
 int opIndex = find_operator(expression, num_tokens); //find index of operator
 int count1=0,count2=0,term1,term2,i,j;

 if(*expression[0] == '(')
 i = 1;
 else
 i = 0;

 while(i <= opIndex)
 i++;
 count1++;
 

 term1 = eval_tokens(expression+1,count1);

 j = opIndex+1;
 while(j < num_tokens)
 count2++;
 j++;
 

 term2 = eval_tokens(expression+opIndex+1,count2); //expression+opIndex+1 points to index after opIndex
 return apply(*expression[opIndex], term1, term2);


int main(void) 
 char*expression = "(", "(", "5", "+", "3", ")", "-", "(", "2", "+", "1", ")", ")";
 printf("result = %dn", eval_tokens(expression, 13));
 return 0;

To use str (or expression) as stack from which you can take items off, I'd make these arguments "modifyable" in the recursive function. Therefore, you could introduce a second function int eval_tokens_recursive(char*** expression, int *num_tokens), which has one more level of indirection and may actually "take items from the stack" by altering the arguments' values.

The code could look as follows. Hope it helps.

int eval_tokens_recursive(char*** expression, int *num_tokens) 

 char *token = **expression;
 if (*num_tokens == 0) 
 printf("expecting more tokens.n");
 exit(1);
 
 if (*token == '(') // begin of expression?
 (*expression)++; // skip opening brace
 (*num_tokens)--;

 // lhs
 int lhs = eval_tokens_recursive(expression, num_tokens);

 // operand
 char operand = ***expression;
 (*expression)++;
 (*num_tokens)--;

 // rhs
 int rhs = eval_tokens_recursive(expression, num_tokens);

 (*expression)++; // skip closing brace
 (*num_tokens)--;

 switch (operand) 
 case '+':
 return lhs + rhs;
 case '-':
 return lhs - rhs;
 case '*':
 return lhs * rhs;
 case '/':
 return lhs / rhs;
 default:
 return 0;
 

 else // not an expression; must be a numeric token
 int operand;
 if (sscanf(token, "%2d", &operand) != 1) 
 printf("expecting numeric value; cannot parse %s.n", token);
 exit(1);
 
 (*expression)++;
 (*num_tokens)--;
 return operand;
 



int eval_tokens(char** expression, int num_tokens) 
 return eval_tokens_recursive(&expression, &num_tokens);


int main() 

 char *expressions = "(", "9", "+", "(", "50", "-", "25", ")", ")";

 int result = eval_tokens(expressions, 9);

 printf("result: %dn", result);