Prefix Evaluation

Can you tell me if this will work? I'm trying to get the logic down for prefix evaluation using a linklist based queue.

The structure I came up with is:

Code:

typedef struct queue
             {
              char cData;
              int nData;
              int flag; /* 1 if char, 2 if number */ 
              struct queue *next;
             }QUEUE;

1) Queue up entire equation.
2) Check element:

a) If its an operator, check to see if next two are operands, if so, deQueue the two operands.
b) Perform the operation.
c) Then put result in the operator's element and change the flag.
d) If two operands are not found, move on to next element, repeat step 2).

3) Repeat step 2 until only one element is left.
4) Display result.

Try following your algorithm with a pen and paper, and see if it works.

Ok, I've been tinkering around with the idea some.

Tried doing this assignment with an array based circular queue. (Before you go (o.0) on me, lemme explain).

Ok, after doing some research, I came across a site that suggested a different method to evaluate prefix equations using queues.

Like so:

1) Queue entire equation
2) Check token.

a) If number, dequeue, then enqueue back on.
b) If operator, check if next two elements are operands, if so, dequeue all three, compute and enqueue result.
c) Else, dequeue, then enqueue.
d) repeat step 2 until only one element left.

3) dequeue result

I worked it out on paper like you suggested, and tried it with the sample equation my teacher gave out, and it works.

Equation tested: - + * 9 + 2 8 * + 4 8 6 3

Result: 159

The program in its current state can handle simple equations, but it will not take much to get it to do whole equations.

Now I've got a new problem, the queue has a character array, and its getting tricky to get the digits in and out, without being treated as something other than digits.

If I use - 4 2 + 7 as input, it works fine, gets a result of 9.

However, if I try to put in extra numbers/operands, the program starts to churn out random letters and numbers (if it doesn't go into an infinite loop).

This is my function for evaluating the prefix equations. Any help would be greatly appreciated!

Code:

int preEval(char buffer[])
    {

	int i, result, length, num1, num2;

	char opr, opr1, temp1, temp2, token[2], item;

	QUEUE q;

	initQueue(&q);

	for (i = 0; i < strlen(buffer); i++)
	    {
		enQueue(&q, buffer[i]);
		}

       do
        {

        length = q.rear - q.front;

        if((!isdigit(q.data[q.front])) && (isdigit(q.data[q.front+1])) && (isdigit(q.data[q.front+2])))
          {
          deQueue(&q, &opr);

          deQueue(&q, &temp1);
          token[0] = temp1;
          token[1] = '\0';
          num1 = atoi(token);

          deQueue(&q, &temp2);
          token[0] = temp2;
          token[1] = '\0';
          num2 = atoi(token);

          if (opr == '+')
            result = num1 + num2;
          else if (opr == '-')
            result = num1 - num2;
          else if (opr == '*')
            result = num1 * num2;
          else if (opr == '/')
            result = num1 / num2;
          else if (opr == '%')
            result = num1 % num2;

            //printf("Result: %d\n", result);

         result = result + '0';

          enQueue(&q, result);
		  }
        else
          {
           deQueue(&q, &opr1);
           enQueue(&q, opr1);
          }
       }
       while(length > 1);
    //printf("num1: %d\n", num1);
    //printf("num2: %d\n", num2);

	while(deQueue(&q, &item))
	     {
	     printf("%c\n", item);
	     }

	return(0);
	}