调车场：操作员缺少参数
我正在实施调车场算法。我无法检测到运算符是否缺少参数。 wikipedia 条目 在这个主题上非常糟糕，并且他们的代码在示例中也会崩溃以下。
例如，3 - (5 + ) 不正确，因为 + 缺少参数。
就在算法到达 ) 之前，运算符堆栈包含 - ( + ，操作数堆栈包含 3 5 。然后是这样的：
- 它从运算符堆栈中弹出
+ - 发现
+是二元运算符 - 弹出两个操作数，应用运算符并将结果 (
8) 推送到操作数堆栈 - 然后它从堆栈中弹出匹配的
(，并继续
那么我如何检测 + 缺少参数？如果您还更新了维基百科，那就额外的荣誉了:-)
I'm implementing the shunting-yard algorithm. I'm having trouble detecting when there are missing arguments to operators. The wikipedia entry is very bad on this topic, and their code also crashes for the example below.
For instance 3 - (5 + ) is incorrect because the + is missing an argument.
Just before the algorithm reaches the ), the operator stack contains - ( + and the operand stack contains 3 5. Then it goes like this:
- it pops
+from the operator stack - discovers that
+is a binary operator - pops two operands, apply operator and push result (
8) to operand stack - then it pops the matching
(from the stack, and continues
So how can I detect that the + is missing an argument? extra kudos if you also update wikipedia :-)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于仅二元运算符的表达式，后缀表达式具有不变式，即在表达式的任何前缀中，操作数的数量>操作员的数量，最终，这个差异恰好是 1。
因此，您可以通过维护操作数数量 - 操作员数量的运行计数来验证调车场每个阶段的 RPN 表达式的有效性。如果该值低于 1，或最终超过 1，则出现错误。
它不会查明错误，但至少让您知道存在错误。
（注：我还没有尝试证明上述事实，但似乎它会起作用）
For binary operator only expressions, the postfix expression has the invariant that in any prefix of the expression, numbers of operands > numbers of operators and in the end, that difference is exactly one.
So you can verify the RPN expression for validity at each stage of the shunting yard by maintaining a running count of number of operands - number of operators. If that drops below one, or becomes more than one at the end, you have an error.
It does not pinpoint the error, but at least lets you know there is one.
(Note: I haven't tried proving the above fact, but seems like it will work)
您可以构建一个状态机。它可以发现令牌有问题的地方。
当您开始阅读表达式时，需要一个前缀运算符或操作数。
如果您阅读前缀运算符，则需要前缀运算符、操作数或左括号。
如果您读取操作数，则需要后缀或中缀运算符或右括号。
如果您阅读后缀运算符，则期望中缀运算符或右括号。
如果您阅读中缀运算符，则需要前缀运算符、操作数或左括号。
如果您阅读左括号，则需要前缀运算符、操作数或左括号。
如果您阅读右括号，则需要后缀或和中缀运算符或右括号。
您可以轻松地将这些 if 转换为 switch。 :)
You can build a state machine. It can spot the tokens where something is wrong.
When you start reading the expression expect a prefix operator or an operand.
If you read a prefix operator expect a prefix operator, operand or opening parenthesis.
If you read an operand expect a postfix or and infix operator or a closing parenthesis.
If you read a postfix operator expect and infix operator or a closing parenthesis.
If you read an infix operator expect a prefix operator, operand or opening parenthesis.
If you read an opening parenthesis expect a prefix operator, operand or opening parenthesis.
if you read a closing parenthesis expect a postfix or and infix operator or a closing parenthesis.
You can turn these ifs to a switch easily. :)