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.

CodePudding user response：

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

CodePudding user response：

Comparing your code

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

with the Wikipedia code 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

It looks like they are functionally identical.

So I suspect the problem is not with the code, but instead with the precedence table. If you have the precedence of and * the wrong way round, then you would get this behaviour. It is easy to get this mixed up as some source have precedence going from tighter binding to loser one and some have the opposite. Compare Wikipedia order of operations and Operator Precedence in Java, use the former.