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(¤t.content)
|| (op_prec(&op_stack.last().unwrap().to_string()) == op_prec(¤t.content)
&& op_asso(¤t.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.
I forgot I had to pop from the operator stack back into the output stack at the end.