Präfix mit einer Warteschlange auswerten?

Question

Ich muss Präfix mit einer Warteschlange (nicht Stack) auswerten. zum Beispiel:

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

Ich denke durch die Warteschlange Schleife um über und über dequeue und enqueue verwenden. Wenn das Muster "operator" + "number" + "number" gefunden wird, wird es dreimal entfernt und das Ergebnis in die Warteschlange eingereiht, bis nur noch eine Zahl in der Warteschlange übrig ist.

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

Mein Algorithmus hat zwei Probleme:

1. Operatoren und Zahlen sind zwei verschiedene Typen und müssen in einer Warteschlange gespeichert werden. Wie kann ich ein "+" in einer int-Warteschlange speichern?
2. 2 3 + ist eine ungültige Eingabe, aber es wird schließlich 5 zurückgeben. 2 und 3 werden in die Warteschlange eingereiht, es wird + 2 3. Wenn die Eingabe ungültig ist, wie kann ich sie verhindern?

Vielen Dank

Answer 1

Answers-
1- Nein, das ist nicht die beste Algorithmus Präfix Eingang (Stack-Ansatz ist besser) zu lösen.
2- Sie können für jeden Operator eine spezielle Nummer angeben (sagen wir -999 für '-').

besserer Ansatz (ohne Stack)
versuchen so etwas wie dieses rekursiven Ansatz

Einfache Rekursion:

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

Dies ist meine rekursive Lösung, die eine Warteschlangenstruktur (last in first out) unter Verwendung von .

Methode 2: Jedes Element wird aus einer alten Warteschlange entfernt und in eine neue Liste eingereiht. Wenn das Muster gefunden wurde, wird es dreimal aus der Warteschlange entfernt und das Ergebnis in die neue Warteschlange eingereiht. Wenn sich die Warteschlangenlänge nicht ändert, melden Sie die ungültige Eingabe.

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