代码之家  ›  专栏  ›  技术社区  ›  Theo Walton

调车场一元链式作业人员的装卸

  •  0
  • Theo Walton  · 技术社区  · 6 年前

    wiki page for shunting yard 因为我在调车场处理链式一元减号运算符时遇到了一个问题,但是wiki算法似乎无法处理它。

    维基算法参考:

    /* 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.
        if the token is a function then:
            push it onto the operator stack 
        if the token is an operator, then:
            while ((there is a function at the top of the operator stack)
                   or (there is an operator at the top of the operator stack with greater precedence)
                   or (the operator at the top of the operator stack has equal precedence and is left associative))
                  and (the operator at the top of the operator stack is not a left bracket):
                pop operators from the operator stack onto the output queue.
            push it onto the operator stack.
        if the token is a left bracket (i.e. "("), then:
            push it onto the operator stack.
        if the token is a right bracket (i.e. ")"), then:
            while the operator at the top of the operator stack is not a left bracket:
                pop the operator from the operator stack onto the output queue.
            pop the left bracket from the stack.
            /* if the stack runs out without finding a left bracket, then there are mismatched parentheses. */
    if there are no more tokens to read:
        while there are still operator tokens on the stack:
            /* if the operator token on the top of the stack is a bracket, then there are mismatched parentheses. */
            pop the operator from the operator stack onto the output queue.
    exit.
    

    假设我有下面的表达式 ---1 1--- ,但实际发生的情况如下:


    迭代1: operator stack: [] output queue: []

    要读取的令牌是 - 所以我们推到运算符堆栈上


    迭代2: operator stack: [-]

    要读取的令牌是 - -


    迭代3: 运算符堆栈:[-] output queue: [-]

    -我们不应该有 - 在输出队列中。

    0 回复  |  直到 6 年前