分流码验证表达式

Question

我们使用分流码算法来计算表达式。我们可以通过简单地应用算法来验证表达式。如果存在缺失操作数、缺失匹配括号和其他内容，则会失败。然而，分流场算法比人类可读的内插有更大的受支持语法。例如，

1 + 2
+ 1 2
1 2 +

所有可接受的方式都提供“12”作为调车场算法的输入。”“12”和“12”不是有效的中缀，但标准调车场算法可以处理它们。该算法实际上并不关心顺序，而是按优先顺序应用运算符，以获取“最近”的操作数。

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

有人知道有什么公开的技术可以做到这一点吗？我们必须同时支持基本运算符、自定义运算符、方括号和函数（具有多个参数）。我在网上没有看到任何比基本操作员更有效的东西。

谢谢

Answer 1

对调车场算法进行了很好的讨论http://www.engr.mun.ca/~theo/Misc/exp\u解析。htm这里介绍的算法使用了操作符堆栈的关键思想，但是有一些语法来知道接下来应该期望什么。它有两个主要函数，一个是表达式，另一个是前缀运算符、变量、数字、括号和函数。前缀运算符总是比二进制运算符绑定得更紧，所以您希望先处理其中任何一个。

如果我们说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()
}

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

Answer 2

我的问题的解决方案是用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.

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