后缀表达式验证？

Question

如何评估包含后缀表达式（例如：3 5 +）的字符串（数组、其他内容），以检查其有效性？

- Matt

---

请更准确地解释你所说的“有效”或“无效”，最好附上示例。 - Norman Ramsey

Answer 1

我这里假设您所说的有效是指执行代码不会导致栈下溢并且将在栈上留下一个单一的值。如果您对有效性有更严格的概念，您需要使用更复杂的检查器。

要检查这种有效性，不需要评估字符串，可以使用计数器而不是堆栈。计数器跟踪如果您进行评估，则会在堆栈上有多少个值。为简化起见，假设只有文字、二元运算符和一元运算符。此算法使用特殊的递减操作：如果递减时计数器低于零，则字符串无效：

1. 将计数器初始化为 0。
2. 当您看到文字时，将计数器增加。
3. 当您看到二元运算符时，将计数器递减两次，然后将其增加。
4. 当您看到一元运算符时，将计数器递减，然后将其增加。
5. 在字符串结尾处，如果计数器为 1，并且它从未低于 0，则字符串有效。

- Norman Ramsey

---

所以，根据您的指示，在每个交替的文字值上，计数器应该减少两次然后再增加？我问这个是因为我没有完全理解它们。 - Khushman Patel

请注意，在步骤3和4中，计数器会先减少再增加。这是有原因的。您必须在每次计数器被减少后检查计数器是否低于0。否则，可能会验证无效的RPN，例如：[2, +, 2]将被视为有效。 - Tim

这将允许{"12", "5.0", "3","+"}成为有效的。 - Mira Welner

@ChristopherConnery 不，这会在执行结束时使计数器=2，而答案说明要检查计数器是否等于1。 - pu239

Answer 2

一个后缀表达式仅当满足以下条件时才有效：

1）前两个元素是操作数(值)；并且

2）最后一个元素是运算符；并且

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

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

- Yoshi

---

您不需要那个额外的第四个条件。如果后缀表达式遵循前三个条件，我们总是可以计算该后缀表达式。 - Kakarot_7

Answer 3

算法：维护一个栈并从左到右扫描后缀表达式 - 如果元素是数字，则将其推入栈中 - 如果元素是运算符O，则弹出两次，分别得到A和B。计算BOA并将其推回到栈中 - 当表达式结束时，栈中的数字是最终答案

//为了有效性，如果在堆栈中只剩下一个数字，则其为正确表达式

//如果在堆栈中剩下多个数字且没有运算符，则为错误表达式

//如果在堆栈中有一个或零个数字且还有运算符，则为错误表达式

- insanely_sin

Answer 4

检查后缀表达式是否有效（如果输入为字符数组）： 1.操作数的数量必须等于运算符的数量加1。 为了检查这一点，需要一个检查变量。 check=0。每个操作数都要增加它，每个运算符都要减少它。如果最终值为1，则表达式有效。

2.数组的前两个元素需要是操作数。没有后缀表达式可以将运算符作为第一个或第二个元素。 通过if控制语句来检查这一点。

- Neel Kapadia