CODEWITHSUNDEEP
algorithmshunting-yardpostfix-notation
Patrick Lorio
Patrick Lorio

Reputation: 5668

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

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#.

Upvotes: 6

Views: 2522

Answers (4)

Paddy3118
Paddy3118

Reputation: 4772

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'

Upvotes: 2

hugomg
hugomg

Reputation: 69934

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
 ...    ...

Upvotes: 8

Ted Hopp
Ted Hopp

Reputation: 234795

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.

Upvotes: 3

moonshadow
moonshadow

Reputation: 89055

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.

Upvotes: 9

Related Questions