parsingrustpostfix-notationshunting-yard

Why does my shunting yard implementation mix operator order?


I have been trying to implement the shunting yard algorithm, but the output of my parser is incorrect.

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

The original equation I am parsing: 1 + 2 * 3

I expected the following output: 1 2 3 * +

Instead I get this: 1 2 3 + *

I think I am going wrong somewhere in my while loop but I don't really know. I tried to follow the example on the Wikipedia article.


Solution

  • I forgot I had to pop from the operator stack back into the output stack at the end.