小编典典

分流场验证表达式

algorithm

我们使用Shunting-Yard算法评估表达式。我们可以通过简单地应用算法来验证表达式。如果缺少操作数,括号不匹配以及其他原因,它将失败。但是,Shunting-Yard算法具有比仅人类可读的前缀更大的支持语法。例如,

1 + 2
+ 1 2
1 2 +

是将“ 1 + 2”作为输入提供给Shunting-Yard算法的所有可接受的方法。’+1 2’和‘1 2 +’不是有效的中缀,但是标准的Shunting-Yard算法可以处理它们。该算法并不真正在乎顺序,它通过抢占“最近”操作数的优先顺序来应用运算符。

我们想将输入限制为有效的人类可读的中缀。我正在寻找一种方法来修改Shunting-Yard算法以使用无效的中缀失败,或者在使用Shunting-Yard之前提供中缀验证。

有人知道有任何公开的技术可以做到这一点吗?我们必须同时支持基本运算符,自定义运算符,方括号和函数(带有多个参数)。除了网上的基本运营商,我还没有看到更多与之合作的产品。

谢谢


阅读 239

收藏
2020-07-28

共1个答案

小编典典

解决我的问题的方法是使用Rici建议的状态机增强Wikipedia上发布的算法。我在这里发布伪代码,因为它可能对其他人有用。

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.

通过查看先前的标记,您可以轻松地区分一元运算符和二进制运算符(我是专门讲负前缀和减法运算符)。如果没有先前的标记,先前的标记是开括号,或者先前的标记是运算符,则您遇到了一元前缀运算符,否则遇到了二进制运算符。

2020-07-28