Gio*_*hal 3 c++ algorithm parsing wikipedia shunting-yard
我正在实施分流码算法.我在检测运营商缺少参数时遇到问题.在维基百科条目是非常糟糕的这个话题,和他们的代码也崩溃了下面的例子.
例如3 - (5 + )是不正确的,因为+缺少一个参数.
就在算法到达之前),运算符堆栈包含- ( +并且操作数堆栈包含3 5.然后它是这样的:
+从操作员堆栈中弹出+是一个二元运算符8)推送到操作数堆栈(从堆栈中弹出匹配,然后继续那么如何才能发现+缺少一个参数呢？额外的荣誉,如果你也更新维基百科:-)
小智 5
对于仅二进制运算符表达式,后缀表达式具有不变量,即在表达式的任何前缀中,操作数的数量>运算符的数量,并且最后,该差异恰好是一个.
因此,您可以通过维持操作数的运行计数(运算符数)来验证RPN表达式在分流码的每个阶段的有效性.如果低于1,或者最后变为多于1,则表示您有错误.
它没有查明错误,但至少让你知道有一个错误.
(注意:我没有尝试证明上述事实,但似乎它会起作用)