分流场验证表达式 [英] Shunting-Yard Validate Expression

问题描述

我们使用Shunting-Yard算法来评估表达式。我们可以通过简单的应用算法验证表达式。如果缺少操作数，错误匹配的括号和其他事情，则失败。然而，Shunting-Yard算法的支持语法更大，而不仅仅是可读的中缀。例如，

We use the Shunting-Yard algorithm to evaluate expressions. We can validate the expression by simply applying the algorithm. It fails if there are missing operands, miss-matched parenthesis, and other things. The Shunting-Yard algorithm however has a larger supported syntax than just human readable infix. For example,

1 + 2
+ 1 2
1 2 +

都是提供1 + 2作为分流场算法输入的可接受的方法。 '+ 1 2'和'1 2 +'不是有效的，但是标准的Shunting-Yard算法可以处理它们。该算法并不在乎订单，它通过优先级顺序来应用运算符，从而获取最近的操作数。

are all acceptable ways to provide '1+2' as input to the Shunting-Yard algorithm. '+ 1 2' and '1 2 +' are not valid infix, but the standard Shunting-Yard algorithm can handle them. The algorithm does not really care about the order, it applies operators by order of precedence grabbing the 'nearest' operands.

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

We would like to restrict our input to valid human readable infix. I am looking for a way to either modify the Shunting-Yard algorithm to fail with non-valid infix or provide an infix validation prior to using Shunting-Yard.

是否有人意识到任何已发表的技术这样做？我们必须支持基本操作符，自定义操作符，括号和函数（带有多个参数）。我没有看到任何与在线基本运算符相关的东西。

Is anyone aware of any published techniques to do this? We must support both basic operator, custom operators, brackets, and functions (with multiple arguments). I haven't seen anything that works with more than the basic operators online.

谢谢

推荐答案

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

The solution to my problem was to enhance the algorithm posted on Wikipedia with the state machine recommended by Rici. I am posting the pseudo code here because it may be of use to others.

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.

您可以轻松区分一元和二进制运算符（我具体来说是负前缀和减法操作员）通过查看以前的令牌。如果没有以前的令牌，以前的令牌是一个开放的括号，或者前一个令牌是一个运算符，那么你遇到一个前缀运算符，否则你遇到了二进制运算符。

You can easily differentiate between unary and binary operators (I'm specifically speaking about the negative prefix and subtraction operator) by looking at the previous token. If there is no previous token, the previous token is an open parenthesis, or the previous token is an operator then you have encountered a unary prefix operator, else you have encountered the binary operator.

这篇关于分流场验证表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！