调车场验证表达式

Question

我们使用调车场算法来评估表达式。我们可以通过简单地应用算法来验证表达式。如果缺少操作数、缺少匹配的圆括号和其他情况，它将失败。然而，Shutting Yard算法支持的语法比人类可读的中缀更大。例如，

1 + 2
+ 1 2
1 2 +

提供"1+2"作为调车场算法输入的所有可接受方式"12"one_answers"12+"不是有效的中缀，但标准的调车场算法可以处理它们。该算法并不真正关心顺序，而是按优先顺序应用运算符，以获取"最近的"操作数。

我们希望将我们的输入限制为有效的人类可读中缀。我正在寻找一种方法，要么修改分流场算法，使其因无效中缀而失败，要么在使用分流场之前提供中缀验证。

有人知道有什么公开的技术可以做到这一点吗？我们必须同时支持基本运算符、自定义运算符、括号和函数(带有多个参数)。除了基本的在线运营商之外，我还没有看到任何能与之合作的东西。

感谢

Answer 1

我的问题的解决方案是用Rici推荐的状态机增强维基百科上发布的算法。我在这里发布伪代码，因为它可能对其他人有用。

Support two states, ExpectOperand and ExpectOperator.
Set State to ExpectOperand
While there are tokens to read:
If token is a constant (number)
Error if state is not ExpectOperand.
Push token to output queue.
Set state to ExpectOperator.
If token is a variable.
Error if state is not ExpectOperand.
Push token to output queue.
Set state to ExpectOperator.
If token is an argument separator (a comma).
Error if state is not ExpectOperator.
Until the top of the operator stack is a left parenthesis  (don't pop the left parenthesis).
Push the top token of the stack to the output queue.
If no left parenthesis is encountered then error.  Either the separator was misplaced or the parentheses were mismatched.
Set state to ExpectOperand.
If token is a unary operator.
Error if the state is not ExpectOperand.
Push the token to the operator stack.
Set the state to ExpectOperand.
If the token is a binary operator.
Error if the state is not ExpectOperator.
While there is an operator token at the top of the operator stack and either the current token is left-associative and of lower then or equal precedence to the operator on the stack, or the current token is right associative and of lower precedence than the operator on the stack.
Pop the operator from the operator stack and push it onto the output queue.
Push the current operator onto the operator stack.
Set the state to ExpectOperand. 
If the token is a Function.
Error if the state is not ExpectOperand.  
Push the token onto the operator stack.
Set the state to ExpectOperand.
If the token is a open parentheses.
Error if the state is not ExpectOperand.
Push the token onto the operator stack.
Set the state to ExpectOperand.
If the token is a close parentheses.
Error if the state is not ExpectOperator.
Until the token at the top of the operator stack is a left parenthesis.
Pop the token off of the operator stack and push it onto the output queue.
Pop the left parenthesis off of the operator stack and discard.
If the token at the top of the operator stack is a function then pop it and push it onto the output queue.
Set the state to ExpectOperator.
At this point you have processed all the input tokens.
While there are tokens on the operator stack.
Pop the next token from the operator stack and push it onto the output queue.
If a parenthesis is encountered then error.  There are mismatched parenthesis.

通过查看前面的标记，您可以很容易地区分一元运算符和二元运算符(我具体说的是负前缀和减法运算符)。如果没有前一个标记，前一个符号是一个开括号，或者前一个记号是一个运算符，则您遇到了一元前缀运算符，否则您遇到了二进制运算符。

Answer 2

关于调车场算法的一个很好的讨论是http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm这里提出的算法使用了运算符堆栈的关键思想，但有一些语法来知道接下来应该期待什么。它有两个主要函数E()，它需要一个表达式；P()，它需要前缀运算符、变量、数字、括号和函数。前缀运算符总是比二进制运算符绑定得更紧，所以你想先处理这个问题。

如果我们说p代表某个前缀序列，而B是一个二进制运算符，那么任何表达式都是形式的

P B P B P

即，您期望的是前缀序列或二进制运算符。从形式上讲，语法是

E -> P (B P)*

p将是

P -> -P | variable | constant | etc.

这转换为psudocode作为

E() {
P()
while next token is a binary op:
read next op
push onto stack and do the shunting yard logic
P()
if any tokens remain report error
pop remaining operators off the stack
}
P() {
if next token is constant or variable:
add to output
else if next token is unary minus: 
push uminus onto operator stack
P()
}

您可以将其扩展为处理其他一元运算符、函数、括号、后缀运算符。