0

给定表达式：

 1/2/3/4*5

它到达表达式的末尾并尝试先将 4 和 5 相乘，这是错误的，因为它开始从堆栈中弹出。我不一定要做RPN，而只是在现场进行评估。我怎样才能防止这种情况？

// Expression was completely read - so we should try and make sense of
// this now
while (operatorStack.size() != 0) {
    ApplyOperation(operatorStack, operandStack);
}

在这一点上，我开始弹出操作符和操作。由于乘法和除法具有相同的存在，它们从乘法开始。

一个痕迹：

1/2/3/4*5
Applying * to 5 and 4
Result: 20
Applying / to 20 and 3
Result: 3/20
Applying / to 3/20 and 2
Result: 40/3
Applying / to 40/3 and 1
Result: 3/40
4

2 回答 2

2

在分流场算法中有一个点，您可以将堆栈顶部的运算符的优先级与输入流中运算符的优先级进行比较，并决定是否弹出堆栈（评估堆叠的运算符，在您的case)，或者推送新的操作符。

如果比较是<或，会有很大的不同<=。其中一个将产生左关联性，另一个将产生右关联性。由于您获得了右关联性并且想要左关联性，因此我猜测（没有看到您的代码）您使用了错误的比较运算符。

顺便说一句，你的教授说得很对。不需要显式生成 RPN，评估算法确实会在到达输入末尾时弹出整个堆栈。（RPN 算法也可以做到这一点；评估算法只是一种捷径。）

于 2013-11-04T23:29:24.547 回答
1

什么operatorStack？调车场算法产生的 RPN 是一个列表，而不是堆栈。它是从左到右处理的，不是FIFO，

于 2013-11-04T22:14:53.593 回答