algorithm - 前缀评估使用队列？

Question

我需要使用队列(而非堆栈)评估前缀。例如:

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

我正在考虑使用 dequeue 和 enqueue 一遍又一遍地遍历队列。如果找到模式“operator”+“number”+“number”，则出队 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);

我的算法有两个问题:

1. 运算符和数字是两种不同的类型，需要保存在一个队列中。如何在 int 队列中保存“+”？
2. 2 3 + 是一个无效的输入，但它最终会返回5。2和3会排到右边，变成+ 2 3。如果输入无效，我该如何防止呢？

非常感谢

Answer 1

答案-
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