prefix evaluate using a queue?

Question

I need to evaluate prefix using a queue (not stack). for example:

 +  3 *  2  1
 is equivalent to 3+(2*1) = 5.

I am thinking about to loop through the queue over and over using dequeue and enqueue. If the pattern "operator" + "number" + "number" if found, dequeue 3 times and enqueue the result until there is only a number left in the queue.

while size(q)>1
    if elements are in this pattern: an operator is followed by 2 numbers. 
        operator <--dequeue(q);
        number1 <--dequeue(q);
        number2 <--dequeue(q);
        int a = apply(operator, number1, number2 );
        enqueue (q, a);
    else if the element is a number or operator:
        element <-- dequeue(q);
        enqueue (q, element);

return dequeue(q);

My algorithm has 2 problems:

operators and numbers are 2 different types and need to be saved in one queue. how can I save a "+" in an int queue?
2 3 + is an invalid input, but it will eventually return 5. 2 and 3 will be enqueued to the right, it becomes + 2 3. If the input is invalid, how do I prevent it?

Many thanks

Tanuj Yadav · Answer 1 · 2017-03-19T07:11:05.267

0

Answers-
1- No this is not the best algorithm to solve prefix input(Stack approach is better).
2- You can give a special number for each operator.(lets say -999 for '-').

Better approach(without stack)
try something like this recursive approach

Simple recursion:

 int c=0;
    Evaluate(input,current_position):
       c++;
      Read a token from input at current pos.
      If the token is a value:
        Return the value of the token
      If the token is a binary operator:
        if(current_position+2 exists)
          Let first_argument = Evaluate(input,current_position+1)
          Let second_argument = Evaluate(input,current_position+2)
          Return apply(operator, first_argument, second_argument)
        else
          invalid expression.

if(c==len(expression)
  valid exp
else
  invalid exp

edited Mar 19 '17 at 07:11

answered Mar 19 '17 at 06:45

Tanuj Yadav

1,259
13
21

any hints for the better algorithm (no stack)? – Di Wang Mar 19 '17 at 06:46
from this post? http://stackoverflow.com/questions/14912045/algorithm-to-evaluate-prefix-expression\ – Di Wang Mar 19 '17 at 06:55
Do u have any trouble understanding it? – Tanuj Yadav Mar 19 '17 at 06:56
I am thinking the recursion method is better in what way? how to implement error check? like 2 3 + – Di Wang Mar 19 '17 at 06:59
for error checking, you can count how many times the recursive function has been called. If it is equal to the length of expression, then it is a valid expression, else it is invalid. Check the edited answer – Tanuj Yadav Mar 19 '17 at 07:06
Isn't recursion algorithm based on a stack data structure? – Di Wang Mar 19 '17 at 08:45
stack will be internally used by the system – Tanuj Yadav Mar 19 '17 at 10:35
you need to use a queue structure to solve this problem. first in first out. – Di Wang Mar 21 '17 at 20:18

score 0 · Answer 2 · answered Mar 26 '17 at 06:33

This is my recursive solution using a queue structure (Last in First out).

Method 2: Each element will be dequeued from an old queue and enqueued to a new list. If the pattern is found, dequeue 3 times and enqueue the result to the new queue. If the queue length doesn't change, report invalid input.

Define: 

1. Given an input string. 
2. Recursive function: int prefix_eval( q ) 
    Base case: if size(q)==1, return dequeue(q); 
    Create a new queue: new_q; 
    int old_qlen = q->qlen; 

    While(size(q)>0) 
        if q->data[0] is an operator, q->data[1] and q->data[2] are numbers.  
            operator <--dequeue(q); 
            number1 <--dequeue(q);
            number2 <--dequeue(q); 
            element = apply(operator, number1, number2 ); 
            enqueue (new_q, element);  
        Else: 
            element = dequeue(q); 
            enqueue(new_q, element); 
        If (old_qlen > new_q->qlen) 
            Prefix_eval(new_q); 
        Else 
            Report invalid input and return  


Start: 
    Create a queue q; 
    Enqueue q with each token from the input
    Prefix_eval(q);

prefix evaluate using a queue?

2 Answers2