检查输入字符串是否是正确的RPN表达式的最快方法是什么？

Question

我遇到了一个任务，它可以检查作为参数传递给您的方法/函数的字符串是否为逆波兰表示法中的正确语句。它可以包含小写字母，操作符号和整数。有没有更快的方法来检查它，而不是单独阅读每个字符，并尝试评估整个表达式？

Answer 1

您不必评估整个表达式，但需要将其分解为令牌，并且必须知道每个运算符的价数（即需要多少操作数）。为简单起见，让一个操作数的价数为0;然后执行以下操作：

Set stack_size to 0; 
For Each token In expression: 
    Set stack_size to stack_size + 1 - valence(token) 
    If stack_size <= 0: Report failure 
If stack_size == 1: Report success 
Else    : Report failure 

使用_作为一元减号的示例。

expression:  3 4 + 1 * _ 
stack_size: 0 1 2 1 2 1 1 -> success 

expression:  2 3 4 + 1 * _ 
stack_size: 0 1 2 3 2 3 2 2 -> failure (not 1 at the end) 

expression:  2 3 + + 1 * _ 
stack_size: 0 1 2 1 0  -> failure (stack_size <= 0) 

Answer 2

您可以使用分析表来识别反向擦亮符号。它需要看每个角色，但速度很快。

Answer 3

Wikipedia有一个很好的算法来解析表达式。除非表达无效（在这种情况下你可能会提前终止），否则你不可能比O（n）做得更好。也就是说，您必须评估字符串中的所有标记以确保其有效。