c - 使用 C 中的队列评估前缀操作

Question

我正在研究前缀评估的问题，我想仅使用队列来评估它们。这是我的伪代码

while Q has more than 1 element
   if the pattern operand, number, number occurs
         op=dequeue(Q)
         num1=dequeue(Q)
         num2=dequeue(Q)
         eval=evaluate(op,num1,num2)
         enqueue(Q,eval)
   else
         elem=dequeue(Q)
         enqueue(Q,elem)

我认为我的逻辑对于格式良好的前缀操作是正确的，但我不确定如何解释无效的前缀语法，例如 10+4。

现在，我的算法会将 10 出队，然后在末尾将其入队，然后它将成为正确的前缀并进行评估，但我不希望它这样做。是否有一些前提条件来确保语法正确？

Answer 1

如果您有一个函数可以弹出队列的第一个元素而不将其出队，则可以在 else 路径中使用它并使用 while(第一个元素不是操作数)来使无效元素出队。这至少可以保证队列中的第一项是操作数。