It is necessary to implement the Shunting-yard algorithm, it is necessary to help in its understanding

Question

I am trying to implement a Shunting-yard algorithm without parentheses, but I find it hard to understand. I tried wikipedia, but the record is really bad. I would not have problems implementing the code, but if I don’t get it, I won’t be able to implement it.

Now: how does this algorithm work?

Here is what I understand:

• Scroll from left to right, all numbers are added to the output queue, all operands are added to the stack. Once you reach the end, you will put all the operands and add them to the output file

  Expression: 2+5*4+3/5 ( = 2+20+0.6 = 22.6 ) Stack: +*+/ ( -> top ) OutputQueue: 5 3 4 5 2 ( -> exits) 

Now I pop the stack and add it to the queue

  OutputQueue: (insert ->) + * + / 5 3 4 5 2 ( -> exit) 

So, as far as I understand, the form should be: 25435 / + * +

Let's try and decide:

  5/3 ~ 1.6 + 4 ~= 5.6 * 5 ~= 28 + 2 ~= 30 (or 30.3 recurring .3 if you insist) 

EDIT: I am sure the reverse Polish notation I used here is correct, so this should not be a question.

I know that I am doing something stupid, but for life I can not understand.

I think this will help the majority if someone can point out an error in my logic, because the algorithm should be good, since it is from Wikipedia, and I saw others pointing me to this. So it should be fine, I just ruined something.

Is this the turn? I'm sure I handle Reverse Polish notation quite well.

Answer 1

You are mistaken:

 Expression: 2+5*4+3/5 

For each token:

  token : 2 outputqueue 2 stack token : + outputqueue 2 stack + token : 5 outputqueue 25 stack + token : "*" "*" has higher predencence as "+", so we push into the stack outputqueue 25 stack +* token : 4 outputqueue 254 stack +* token : "+" "+ "has lower predencence as "*", we pop "*" from the stack. "+" has same predecence as "+", so we pop "+" from the stack then add the current token "+" in the stack outputqueue 254*+ stack + token : 3 outputqueue 254*+3 stack + token : "/" "/" has lower predencence as "+", we push "/" into the stack outputqueue 254*+ stack +/ token : 5 outputqueue 254*+35 stack +/ 

The expression is complete, pull the stack:

 output 254*+35/+ 

---

Payment:

 5*4 = 20 2+20 = 22 3/5 = 0.6 22 + 0.6 = 22.6 

Answer 2

I'm not sure that the algorithm you want is simple enough - have you read the entire wiki article that you link to? In particular, see the “ Detailed Algorithm ” section has much in common with the priority of the operator, which, I think, you discard in your current implementation. My suggestion is to go through this section one step at a time, following the steps (and compared to the example below as necessary) to try and find a suitable form for this problem. Once you do this, it will hopefully help you understand the whole algorithm.