c++ - 调车场:缺少运算符(operator)参数

Question

我正在实现 shunting-yard algorithm .我无法检测到运算符何时缺少参数。 wikipedia entry在这个主题上非常糟糕，他们的代码也因下面的示例而崩溃。

例如 3 - (5 + ) 是不正确的，因为 + 缺少参数。

就在算法到达)之前，运算符堆栈包含- ( +，操作数堆栈包含3 5。然后它去像这样:

• 从操作符栈中弹出+
• 发现+是一个二元运算符
• 弹出两个操作数，应用运算符并将结果(8)压入操作数栈
• 然后它从堆栈中弹出匹配的(，然后继续

那么我怎样才能检测到 + 缺少一个参数呢？如果你还更新维基百科，额外的荣誉:-)

Answer 1

对于只有二元运算符的表达式，后缀表达式具有不变性，即在表达式的任何前缀中，操作数的数量 > 运算符的数量，最后，差值正好是一个。

因此，您可以通过维护操作数数量 - 运算符(operator)数量的运行计数来验证 RPN 表达式在调车场每个阶段的有效性。如果它低于 1，或最后变得大于 1，则说明您有错误。

它不会查明错误，但至少让您知道有一个错误。

(注意:我还没有尝试证明上述事实，但看起来它会起作用)