Talk:Shunting yard algorithm

Hi.

Have you carefully read the Summary section here?

I will reproduce it here to you:

Start off with an empty output stream and an empty stack. Repeatedly read a symbol from the input.

• If it is part of a number (i.e., a digit or a decimal separator), then keep reading tokens until an operand or parenthesis is encountered, and convert the entire string just read into a number, and transfer the number to the output stream.
• If it is a left-associative operator, then repeatedly pop from the stack into the output stream until either the stack becomes empty or the top of the stack is a parenthesis or a lower-precedence operator.
• If it is a right-associative operator, then repeatedly pop from the stack into the output stream until either the stack becomes empty or the top of the stack is a parenthesis or an operator of lower or equal precedence.
• If it is an opening parenthesis, push it onto the stack.
• If it is a closing parenthesis, repeatedly pop operators from the stack into the output stream until an opening parenthesis is encountered. Pop the opening parenthesis off the stack, but do not emit it into the output stream.

I'm not an english native, but usually I haven't any problems with this kind of stuff. Now, I will point you the problem I see here:

It says that «We start with an empty output and an empty stack». Empty output. Empty stack. OK, right? Well. Check all the points and point me in what part it says that we need to push anything different from an «opening parenthesis» into the stack. You see the problem? According this Summary we only need to push «opening parenthesis» into the stack. The same stack what this says that start empty.

So, in resume: we have an empy stack in where we only push some opening parenthesis. What unusual trick is used here to pop operators from an stack where we only pushed opening parenthesis? This Summary is misleading/hard to understand.

But if I try to understand this reading the previous section, How to handle parentheses, I'm no more lucky.

That section states that:

an opening parenthesis behaves like the beginning of an expression, in the sense that none of the operands after belong to any of the operands before it; thus, when we encounter one, we push it onto the stack, and, until the corresponding closing parenthesis is encountered, we cannot examine any of the operators beneath it. So in the expression 1*2+3, we would normally pop off the * after encountering the +; but if we have 1*(2+3) instead, then, upon reaching the +, the stack will have ( on the top and * below it; so here we do not pop off anything at all.

When we encountered what? And operand, the text said. So here we are pushing operands (this isn't said in the summary neither) onto the stack, not operators. Still no one single operator pushed to the stack.

It's so difficult to grasp this when it's so confussing. I also checked previously of this the english wikipedia entry and there they're speaking about an output queue (what's different from an stack) and an stack. With so many differences I still don't know about a secure an plain explanation about the steps of this algorithm, because every site I check explains different steps and mixes/omits things in the steps.

Anyone is so kind to edit the text of the Summary for it being a real summary? Or explaining what I'm missing? Because the more explanations I read about this, less clear I have this.

Thanks :).