后缀表示法验证？

Question

什么是评估包含后缀表达式(例如:3 5 +)的字符串(数组,某些东西)来检查有效性的好方法？

Answer 1

我在这里假设你的意思是有效的是执行代码永远不会使堆栈下溢并在堆栈上留下一个值.如果你有更严格的有效性概念,你需要一个更复杂的检查器.

如果要检查此类有效性,则无需评估字符串,您可以使用计数器,而不是堆栈.计数器跟踪您评估时堆栈上的值的数量.为简化起见,假设您只有文字,二元运算符和一元运算符.此算法使用特殊的递减操作:如果递减时,计数器低于零,则字符串无效:

请注意，在第 3 步和第 4 步，计数器先递减，然后递增。这是有原因的。每次计数器递减后，您都必须检查计数器是否低于 0。否则有可能验证无效的 RPN，例如：`[2, +, 2]` 将是有效的。 (2认同)

Answer 2

后缀表达式有效当且仅当：

1) 前两个元素是操作数（值），并且

2) 最后一个元素是一个运算符，并且

3) 对于每 n 个值，有 n-1 个运算符，并且

4) 在 n 个元素的列表中，从索引 i = 0 开始，对于 i < n-1 （倒数第二个元素），每组由 k 个值组成的元素（对于 k > 1 ）后面跟着 (k-1 ) 运算符。当 k = 1 时，后面的运算符数量 = k = 1。