préfixe évaluer en utilisant une file d'attente?

Question

Je dois évaluer le préfixe en utilisant une file d'attente (pas de pile). par exemple:

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

Je pense à faire une boucle dans la file d'attente à plusieurs reprises à l'aide dequeue et enqueue. Si le motif "opérateur" + "numéro" + "numéro" est trouvé, déqueuez 3 fois et mettez en file d'attente le résultat jusqu'à ce qu'il ne reste qu'un nombre dans la file d'attente.

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); 

Mon algorithme a 2 problèmes:

1. opérateurs et les numéros sont 2 différents types et doivent être enregistrés dans une file d'attente. comment puis-je enregistrer un "+" dans une file d'attente int?
2. 2 3 + est une entrée invalide, mais elle finira par retourner 5. 2 et 3 seront placés dans la file d'attente à droite, cela devient + 2 3. Si l'entrée est invalide, comment l'empêcher?

Un grand merci

Answer 1

Answers-
1- Non, ce n'est pas le meilleur algorithme pour résoudre l'entrée de préfixe (approche Stack est mieux).
2- Vous pouvez donner un numéro spécial pour chaque opérateur (disons -999 pour '-').

Une meilleure approche (sans pile)
essayer quelque chose comme cette approche récurrente

récursivité simple:

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 

Answer 2

Ceci est ma solution récursive en utilisant une structure de file d'attente (dernière sortie de la première) .

Méthode 2: Chaque élément sera retiré de la file d'attente d'une ancienne file d'attente et mis en file d'attente dans une nouvelle liste. Si le motif est trouvé, déqueue 3 fois et met le résultat dans la nouvelle file d'attente. Si la longueur de la file d'attente ne change pas, signalez une entrée non valide.

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);