Thread: Prefix Evaluation

  1. #1
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23

    Question 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.
    Viva la Tutorial
    What is the meaning of life? 42 of course!

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Try following your algorithm with a pen and paper, and see if it works.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23

    Thumbs up

    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.
    Viva la Tutorial
    What is the meaning of life? 42 of course!

  4. #4
    Registered User jcramer's Avatar
    Join Date
    Oct 2003
    Posts
    23

    Question Another problem....

    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);
    	}
    Viva la Tutorial
    What is the meaning of life? 42 of course!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. longest prefix
    By Marksman in forum C Programming
    Replies: 1
    Last Post: 03-14-2009, 11:19 PM
  2. Atomic Operations
    By Elysia in forum Windows Programming
    Replies: 27
    Last Post: 03-27-2008, 02:38 AM
  3. which to prefix with std:: ??
    By wakish in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2005, 02:58 PM
  4. Prefix Expressions
    By mannyginda2g in forum C++ Programming
    Replies: 4
    Last Post: 03-19-2004, 01:30 AM
  5. Performance Evaluation
    By rick barclay in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 09-16-2001, 10:16 AM