接頭辞はキューを使用して評価されますか？

Question

キュー（スタックではない）を使ってプレフィックスを評価する必要があります。

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

デキューとエンキューを使用してキューを何度もループすることを考えています。パターン "operator" + "number" + "number"が見つかった場合は、3回デキューし、キューに残っている数字だけが残るまで結果をエンキューします。

1. 演算子と数値が異なる2種類あり、1つのキューに保存する必要があります

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

   私のアルゴリズムは、2つの問題があります。どのようにして "+"をint待ち行列に保存できますか？

2. 2 3 +は無効な入力ですが、最終的には5を返します.2と3は右にエンキューされ、+ 2になります。3入力が無効の場合はどうすればよいですか？

感謝

Answer 1

Answers-
1-ありません、これは接頭入力を（スタックアプローチが優れている）を解決するための最良のアルゴリズムではありません。
2各オペレータに特別な番号を付けることができます（ ' - 'は-999とします）。これは、キュー構造（第一の最後のアウト）を使用して、私の再帰的なソリューションです

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

： （スタックなし）

より良いアプローチ
は何か

この再帰的なアプローチのような単純な再帰を試してみてください。

方法2： 各要素は古いキューからデキューされ、新しいリストにエンキューされます。パターンが見つかった場合は、3回デキューし、その結果を新しいキューにエンキューします。キュー長が変更されない場合は、無効な入力を報告します。

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