为什么我的调车场实施混合运营商命令？

Question

我一直在尝试实现 the shunting yard algorithm，但我的解析器输出不正确。

let mut stack: Vec<String> = vec![];
let mut op_stack: Vec<String> = vec![];

for current in sub_tree {
    if current.tok_type == TokenType::NUMBER || current.tok_type == TokenType::NEGNUMBER {
        self.parse();
        stack.push(current.content.clone());
    }
    if current.tok_type == TokenType::SUBBIN
        || current.tok_type == TokenType::PLUSBIN
        || current.tok_type == TokenType::DIVBIN
        || current.tok_type == TokenType::MULBIN
    {
        while op_stack.len() > 0 && op_stack.last().unwrap().to_string() != "(" {
            if op_prec(&op_stack.last().unwrap().to_string()) > op_prec(&current.content)
                || (op_prec(&op_stack.last().unwrap().to_string()) == op_prec(&current.content)
                    && op_asso(&current.content) == "left")
            {
                stack.push(op_stack.pop().unwrap().to_string());
            } else {
                break;
            }
        }
        op_stack.push(current.content.to_string())
    }
}

我解析的原方程：1 + 2 * 3

我期望得到以下输出：1 2 3 * +

相反，我得到了这个：1 2 3 + *

我想我在 while 循环的某个地方出错了，但我真的不知道。我尝试按照维基百科文章中的示例进行操作。

Answer 1

我忘记了我必须在最后从运算符堆栈弹出回到输出堆栈。

Answer 2

比较你的代码

   if current.tok_type == TokenType::SUBBIN
        || current.tok_type == TokenType::PLUSBIN
        || current.tok_type == TokenType::DIVBIN
        || current.tok_type == TokenType::MULBIN
    {
        while op_stack.len() > 0 && op_stack.last().unwrap().to_string() != "(" {
            if op_prec(&op_stack.last().unwrap().to_string()) > op_prec(&current.content)
                || (op_prec(&op_stack.last().unwrap().to_string()) == op_prec(&current.content)
                    && op_asso(&current.content) == "left")
            {
                stack.push(op_stack.pop().unwrap().to_string());
            } else {
                break;
            }
        }
        op_stack.push(current.content.to_string())
    }

使用维基百科代码https://en.wikipedia.org/wiki/Shunting-yard_algorithm

- an operator o1:
    while (
        there is an operator o2 other than the left parenthesis at the top
        of the operator stack, and (o2 has greater precedence than o1
        or they have the same precedence and o1 is left-associative)
    ):
        pop o2 from the operator stack into the output queue
    push o1 onto the operator stack

看起来它们在功能上是相同的。

所以我怀疑问题不在于代码，而在于优先级 table。如果您将 + 和 * 的优先级设置错了，那么您将得到这种行为。很容易混淆这一点，因为一些源优先从更紧密的绑定到失败者，而有些则相反。比较Wikipedia order of operations and Operator Precedence in Java，用前者。

为什么我的调车场实施混合运营商命令？

Why does my shunting yard implementation mix operator order?

parsing

postfix-notation

shunting-yard

rust