评估后缀表达式

Question

我必须编写一个程序，将中缀转换为后缀，然后计算后缀表达式。我已经完成了转换部分。但是我对评估部分有点困惑。计算表达式的方法采用后缀表达式的链表表示。这让我有点困惑。该方法的 header 如下所示：

public static String evaluatePostfix(StringList postfix)

所以，我是否必须遍历链表并对其进行评估？

提前致谢。

Answer 1

是的，你需要迭代链表，并评估它。评估后缀表达式的经典方法是使用 堆栈 。算法如下：

• 对于列表中的每个元素，检查其类型
• 如果元素代表一个数字，将其压入堆栈
• 如果该元素是一个操作，则根据操作的类型从堆栈中弹出一个或两个元素，执行操作，并将结果推回堆栈
• 一旦循环结束，栈上就会有一个元素；这就是你的结果。

如果您的操作在任何时候都无法在堆栈中找到足够的参数，则正在评估的表达式无效。当循环完成时堆栈没有恰好一个元素的情况也是如此。