调车场算法，有什么变化吗? [英] shunting Yard Algorithm, any changes?

问题描述

我已经根据Wikipedia中提到的内容在C ++ 11中实现了调车场算法:

I have implemented shunting yard algorithm in C++11 according to what is mentioned in wikipedia:

此实现未实现复合函数，具有可变数量的参数的函数，和一元运算符.

This implementation does not implement composite functions,functions with variable number of arguments, and unary operators.

while there are tokens to be read:
    read a token.
    if the token is a number, then:
        push it to the output queue.
    else if the token is a function then:
        push it onto the operator stack 
    else if the token is an operator then:
        while ((there is a operator at the top of the operator stack)
              and ((the operator at the top of the operator stack has greater precedence)
               or (the operator at the top of the operator stack has equal precedence and the token is left associative))
              and (the operator at the top of the operator stack is not a left parenthesis)):
            pop operators from the operator stack onto the output queue.
        push it onto the operator stack.
    else if the token is a left parenthesis (i.e. "("), then:
        push it onto the operator stack.
    else if the token is a right parenthesis (i.e. ")"), then:
        while the operator at the top of the operator stack is not a left parenthesis:
            pop the operator from the operator stack onto the output queue.
        /* If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. */
        if there is a left parenthesis at the top of the operator stack, then:
            pop the operator from the operator stack and discard it
/* After while loop, if operator stack not null, pop everything to output queue */
if there are no more tokens to read then:
    while there are still operator tokens on the stack:
        /* If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses. */
        pop the operator from the operator stack onto the output queue.
exit.

如您所见，提到该算法不会处理一元运算符，假设我有一个比所有其他运算符都要强的!，我应该对我的算法进行哪些更改如果有的话?

As you can see it's mentioned that this algorithm doesn't deal with unary operator, suppose I have one ! which is stronger than all other operator, what changes should I make to my algorithm if any?

一些法律使用!运算符的示例:

Some Legal Examples of using ! operator:

!1
! 1
! (1)
!(  1 + 2)

还有一个小问题，该算法是否处理像1==2这样的错误语法(我想是的)?

Plus one small question, does this algorithm deal with wrong syntax like 1==2 (I supposed that yes it does)?

推荐答案

问题1:

为了使您的算法起作用，您应该在 infix 运算符之前解析 prefix 运算符!，只需将其视为开放括号(然后您需要调整堆栈虚拟机以允许此类操作符). 我建议将括号的if检查移到infix运算符之前(它变化不大，但可读性更高). 我还要说，如果您想同时实现 operator优先级， postfix运算符和 mixfix运算符之类的功能，则应该切换到普拉特解析器(更容易使用).

In order to make your algorithm work you should parse the prefix operator ! before the infix operators, simply treating it as if it was an open parenthesis ( (then you need to tweak the stack virtual machine to allow this kind operator). I suggest moving the if check for the parenthesis before the infix operator (it doesn't change much but it's more readable). I will also say that if you want to achieve things like operator precedence, postfix operators and mixfix operators all together you should switch to a Pratt parser (which is much easier to work with).

问题2:

这里的解析器不处理像1 == 2这样的操作，它只解析它们.基于堆栈的虚拟机处理它们，并且1 == 2是一个完全好的比较，因为它应该返回false.如果您打算同时具有布尔表达式和算术表达式，则可以这样做.

The parser here doesn't deal with operations like 1 == 2, it only parses them. The stack based virtual machine deals with them and 1 == 2 is a completely fine comparison since it is supposed to return false. This if you plan to have boolean expressions as well as arithmetic expressions.

调整" (部分解决了该问题):将运算符视为正确的关联，并使其优先级高于其他运算符.

The "tweak" (which partially solves the issue): consider the operator as right associative and make its precedence higher than the other operators.

(如 @dure 的注释中所指出的)这只是一个调整，因为il将导致解析器解析前缀和后缀运算符而没有区别，并且需要进一步注意避免错误.

This (as pointed out in the comments by @dure) is just a tweak, since il will cause the parser to parse prefix and postfix operators without distinction and needs further care to avoid bugs.

这篇关于调车场算法，有什么变化吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！