我需要使用队列（不是堆栈）评估前缀。例如：
+ 3 * 2 1
is equivalent to 3+(2*1) = 5.
我正在考虑使用出队和入队一遍又一遍地遍历队列。如果模式“操作员”“数字”“数字”如果找到，则出队3次并将结果入队，直到队列中只剩下一个数字。
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个问题：
非常感谢
答案-
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
这是我使用队列结构（后进先出）的递归解决方案。
方法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);
