c++ - 调车场：缺少操作员的参数

Question

我正在实施调车场算法。我无法检测何时缺少运算符的参数。维基百科条目在这个主题上非常糟糕，并且他们的代码在下面的示例中也崩溃了。

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

就在算法到达之前)，运算符堆栈包含- ( +并且操作数堆栈包含3 5。然后它是这样的：

那么我怎样才能检测到+缺少参数呢？如果您还更新了维基百科，那就再好不过了 :-)

score 5 · Accepted Answer

对于仅二元运算符的表达式，后缀表达式具有在表达式的任何前缀中，操作数的数量 > 运算符的数量的不变量，并且最后，该差异恰好是一。

因此，您可以通过维护操作数数量的运行计数 - 运算符数量来验证 RPN 表达式在调车场的每个阶段的有效性。如果该值低于 1，或者最终超过 1，则说明出现错误。

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

（注意：我没有尝试证明上述事实，但似乎它会起作用）

score 1 · Accepted Answer

您可以构建状态机。它可以发现有问题的令牌。

当您开始阅读表达式时，需要一个前缀运算符或操作数。如果您阅读前缀运算符，则需要前缀运算符、操作数或左括号。

如果您阅读操作数，则需要后缀或中缀运算符或右括号。

如果您阅读后缀运算符，则期望和中缀运算符或右括号。

如果您阅读中缀运算符，则需要前缀运算符、操作数或左括号。

如果您阅读左括号，则需要前缀运算符、操作数或左括号。

如果您阅读右括号，则需要后缀或中缀运算符或右括号。

您可以轻松地将这些 if 转换为开关。:)

2 回答 2