Trouble understanding what to do with output of shunting-yard algorithm

Question

I've been looking at the wiki page: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

I've used the code example to build the first part, basically I can currently turn :

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 into 3 4 2 * 1 5 − 2 3 ^ ^ / +

But I don't know how to then use 3 4 2 * 1 5 − 2 3 ^ ^ / + to obtain 3.00012207

And the example code and explanation on wiki aren't making any sense to me.

Could someone please explain how to evaluate 3 4 2 * 1 5 − 2 3 ^ ^ / + and produce the answer. Thanks in advance. I don't need a code example just a good explanation or a breakdown of an example.

Not that it matters but I am working .net C#.

Proto

Answer 1

The purpose of the shunting yard algorithm is that its output is in Reverse Polish Notation, which is straightforward to evaluate:

• create a stack to hold values
• while there is reverse polish notation input left:
  • read an item of input
  • if it is a value, push it onto the stack
  • otherwise, it is an operation; pop values from the stack, perform the operation on those values, push the result back
• when there's no input left, if the expression was well formed, there should be exactly one value on the stack; this is the evaluated result.

Ample

A stack is a proper data structure to achieve this, what kind of collection would you suggest to use in Java (if you know it)? A LinkedList or a Deque? I know Java has a Stack<E> class but I read that it is not advaisable to use because of the synchronization. – Ewald

Answer 2

The post-fix notation is how you do the math in, say, a HP calculator.

Keep a stack, whenever you get a number add it to the top. Whenever you get an operator consume inputs from the top and then add the result to the top

token stack
      *empty*
 3    3         //push numbers...
 4    3 4
 2    3 4 2
 *    3 8       //remove 4 and 2, add 4*2=8
 1    3 8 1
 5    3 8 1 5
 -    3 8 -4
 2    3 8 -4 2
 3    3 8 -4 2 3
 ^    3 8 -4 8
 ...    ...

Kaifeng

Answer 3

Process the elements 3 4 2 * 1 5 − 2 3 ^ ^ / + left-to-right as follows:

1. Initialize a stack to hold numbers.
2. If the element is a number, push it onto the stack.
3. if the element is an operator, remove the top two elements from the stack, apply the operator to those two elements, and push the result onto the stack.

When you get to the end, the stack should have a single element which will be the result.

Priscella

Answer 4

I see I am a bit late to the party.

I saw the question and went off on a tangent writing a couple of tasks for Rosetta Code. It just so happens that this task might be what you are after. It gives an annottated table of what happens when calculating the value of an RPN expression, token by token.

Here is a sample of its output:

For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'

TOKEN           ACTION                 STACK      
3     Push num onto top of stack 3                
4     Push num onto top of stack 3 4              
2     Push num onto top of stack 3 4 2            
*     Apply op to top of stack   3 8              
1     Push num onto top of stack 3 8 1            
5     Push num onto top of stack 3 8 1 5          
-     Apply op to top of stack   3 8 -4           
2     Push num onto top of stack 3 8 -4 2         
3     Push num onto top of stack 3 8 -4 2 3       
^     Apply op to top of stack   3 8 -4 8         
^     Apply op to top of stack   3 8 65536        
/     Apply op to top of stack   3 0.0001220703125
+     Apply op to top of stack   3.0001220703125  

 The final output value is: '3.0001220703125'

Endothermic