Shunting-Yard 验证表达式

Question

我们使用Shunting-Yard算法来计算表达式。通过应用该算法，我们可以验证表达式。如果存在缺少操作数、括号不匹配和其他问题，则会失败。然而，Shunting-Yard算法支持的语法比人类可读的中缀更广泛。例如，

1 + 2
+ 1 2
1 2 +

所有这些都是向 Shunting-Yard 算法提供“1+2”输入的可接受方式。“+ 1 2”和“1 2 +”不是有效的中缀表示法，但标准的Shunting-Yard算法可以处理它们。该算法实际上并不关心顺序，它根据优先级顺序应用运算符并获取“最近”的操作数。

我们想将输入限制为有效的人类可读中缀表示法。我正在寻找一种修改 Shunting-Yard 算法使其无法处理非有效中缀或在使用 Shunting-Yard 之前提供中缀验证的方法。

是否有人知道任何已发布的技术来做到这一点？我们必须支持基本运算符、自定义运算符、括号和函数（带有多个参数）。我在网上没有看到可以处理超出基本运算符的东西。

谢谢

- denver

---

你可以使用中缀运算符解析器，这样做当然不会利用你已经存在的逆波兰式解析器，但它会起作用。 - ryanyuyu

可能是Shunting-yard算法中处理额外运算符的重复问题。 - rici

@rici，也许吧，我现在正在查看其他的问题和答案。 - denver

@denver：我本来想直接回答这个问题，但是我记得我已经回答过了，所以我只是把你引用到我的答案。我建议的状态机也是回答“如何处理逆波兰算法中的一元减号”的答案，所以你可能已经实现了类似的东西。链接的答案还试图区分用于分组的()和用于函数调用的()；如果对你没有用处，你可以忽略这部分，但它实际上并不比一元减号问题更复杂。 - rici

@rici 看起来状态机（2个状态，期望操作符和期望操作数）是解决我的问题的方案。在我们支持的每种令牌类型（常量、变量、函数、二元运算符、一元运算符、开括号、闭括号和参数分隔符）的if语句中，如果读取令牌时不处于预期状态，我们基本上会抛出异常，然后将状态设置为下一个期望的状态。 - denver

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.

你可以通过查看前一个标记来轻松区分一元和二元运算符（我特别指的是负前缀和减法运算符）。如果没有前一个标记，前一个标记是开括号或前一个标记是运算符，则遇到了一元前缀运算符，否则遇到了二元运算符。

- denver

---

我认为在我们退出第一个 while 循环后，我们必须添加一行代码 如果状态不是 ExpectOperator，则报错。这可以确保最后一个标记是操作数。 - Bernard

此外，还必须检查最后一个添加到堆栈的标记是否不是一元标记。否则，类似于 5++++++6 的表达式仍然是有效的。 - Arxeiss

Answer 2

一个关于Shunting Yard算法的好讨论可以在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.

这句话的意思是伪代码，可以转化为以下形式：

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()
}

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

- Salix alba

---

谢谢回答。rici提供的答案提供了类似的方法。 - denver