Difference between revisions of "Postfix Notation"

Revision as of 00:14, 19 October 2011

Lesson

PostFix - By YmxldnB4 and patri0t

1.0 - Introduction

This lesson is regarding Postfix Notation (also known as Reverse Polish Notation or RPN), after some polish guy who invented the polish notation (which is basically the reverse of this, called "prefix"). Traditionally, you write mathematic expressions like "number operator number", eg "3 + 4". This notation is called infix (as the operator is in between the two numbers). In postfix notation, the operator is written after it's two 'numbers' or operands. So you write "3 4 +". This has the advantage that you do not need to remember the operator while you are reading the expression from left to right. Instead, you only have to remember the number, and you can calculate as soon as you see the operator. The most obvious advantage is that, in this way, there is no need to specify operator precedence(using parentheses).

For example, if I write "3 - 4 * 5", this can mean both "(3 - 4) * 5" and "3 - (4 * 5)", you need to use some mnemonics or just remember to get the right interpretation.

Especially when I have larger formulas, this can become a problem. In postfix, I would just write "3 4 5 * -", this would evaluate as "(3 (4 5 *) -)". You can reduce this to "(3 20 -)", so you get "-17". In the case of "(3 - 4) * 5", I would have written "3 4 - 5 *". This would reduce to "-1 5 *", so that makes "-5".

Not only is this notation useful for humans, it is also useful for computers. First of all, as the order of operations is clear, there is no need for any complicated parsing. Secondly, postfix expressions can be easily evaluated using a stack.

2.0 - "So WTF is a stack?"

For those of you who are not familiar with computer science, I'll explain. A stack is a FILO (meaning first-in last-out) queue. This means that the first item you put on it, will be the last to come out. Consequently, it means that the last item you put on it, will be the first to come out.Compare it with those spring-loaded dish stacks at restaurants. If someone places a dish on it, it will always be the first one that can be gotten from it(it is used in assembly too, so expect hatter to talk about it a bit more). We'll call the act of putting something on the top of the stack 'pushing', and the act of getting something off the top of the stack 'popping'. Using a stack, we can evaluate postfix expressions rather easily. We can go over all the items in the expression from left to right.

2.1 - PostFix Expression

When you encounter a number, you push it to the stack. When you encounter an operator, you pop 2 items (or more/less, depending how many the operator requires) off the stack. Then we calculate the result and push that back on the stack.When you are done with the whole expression, you will (in a valid expression at least) have only one item on the stack. This is the result of the computation]

2.2 - Example

So now...example time! we take the expression 3 + 5 * ((-2)^7 - (3/2)). First, we convert it to postfix. So let's convert it. We get 3 5 -2 7 ^ 3 2 / - * + Now we go over that expression (I will use () to point out what item we are currently at.)

.__________________________________.
|(3) 5  -2  7  ^  3  2  /  -  *  + |   A number. We push it to the stack, making the stack contain 3,
| 3 (5) -2  7  ^  3  2  /  -  *  + |   Another number, the stack is now    3, 5
| 3  5 (-2) 7  ^  3  2  /  -  *  + |   Another number, making              3, 5, -2
| 3  5  -2 (7) ^  3  2  /  -  *  + |                                       3, 5, -2, 7
| 3  5  -2  7 (^) 3  2  /  -  *  + |   Operator! (-2)^7 = -128.            3, 5, -128.
| 3  5  -2  7  ^ (3) 2  /  -  *  + |   Another number,                     3, 5, -128, 3
| 3  5  -2  7  ^  3 (2) /  -  *  + |                                       3, 5, -128, 3, 2
| 3  5  -2  7  ^  3  2 (/) -  *  + |   Operator! 3 / 2 = 1.5. Stack is now 3, 5, -128, 1.5
| 3  5  -2  7  ^  3  2  / (-) *  + |   Operator! -128-1.5 = -129.5. Stack: 3, 5, -129.5
| 3  5  -2  7  ^  3  2  /  - (*) + |   Operator! -129.5*5 = -647.5.        3, -647.5
| 3  5  -2  7  ^  3  2  /  -  * (+)|   Final operator. -647.5 + 3 = -644.5. Stack is now -644.5.
|__________________________________|             

Take some time to follow that now, it should make sense.

2.3 - Back to PostFix

If you were a computer, and your programmer was not some kind of geek that decides to use binary trees, you'd most certainly be using that method. But most of you are different kinds of computers (that is another topic for debate). You're all human. Humans can do it a bit faster. Basically, you just take groups of number number operator and replace that with its result.

Example: let's use the same expression: "3 5 -2 7 ^ 3 2 / - * +". This will evaluate to: "number1 operator number2". So we start with: "3 5 -2 7 ^ 3 2 / - * +". We first replace the -2 7 ^ with -128, and get 3 5 -128 3 2 / - * +. Secondly, we replace the 3 2 / with 1.5, and get 3 5 -128 1.5 - * +. Thirdly, replace the -128 1.5 - with -129.5 and get 3 5 -129.5 * +. Then we replace the 5 -129.5 * with -647.5 and get 3 -647.5 +. Finally, we replace 3 -647.5 + with -644.5 and we're done :-)

This notation may look harder, but that is mainly because you have spent most of your life using infix notation. It is in fact easier, as you do not need to remember any order of operations. Patri0t will now talk about evaluation using binary trees now.

3.0 - Binary Trees

Now, we will be using binary trees to convert an infix expression to postfix expression. For those who don't know what a binary tree is, a binary tree is basically a data structure in which each node has at most, 2 child nodes. For excellent detail check out the wikipedia page: https://secure.wikimedia.org/wikipedia/en/wiki/Binary_tree. For those experienced in this area, this is about generating postfix by post-order traversal of an abstract syntax tree generated by an operator-precedence parser.

For a binary tree, you can have 2 types of traversal, which means to visit each node once.: 1) Breadth first search, 2) depth first search. Breadth first search can be further divided into 3 types: 1) pre-order traversal, 2) in-order traversal, 3) post-order traversal. Here, we are concerned only with postorder traversal. In this type of traversal, we first visit the left node, the right node and then the root. Consider this image:

._________________.
|......(2)........|
|....../.\........|
|....(7).(5)......|
|..../.\...\......|
|..(2).(6).(9)....|
|....../.\...\....|
|....(5).(11)(4)..|
|_________________|
    

Assume this has only 3 nodes, 2, 7 and 5 for the sake of understanding. 2 -> root node, 7 -> left node, 5 -> right node For this binary tree, postorder traversal, following the rule, "left right root", will be 752.

3.1 - Example

Using the wiki example to help generate a binary tree, do postorder traversal on it and get a postfix expression. Consider "5 + ((1 + 2) * 4) - 3", that's an infix expression which we'll map to a btree. A point to remember here is the operator is always root node and the operands are child nodes.

Starting from the innermost brackets, we make 1 as left node, 2 as right node and + as root node. Continuing similarly, + is left node, 4 is right node and * is root node. Now, 5 is left node, * is right node and + is root node. The + used above is left node, 3 is right node and - is the root node.

._____________.
|......(-)....|
|....../.\....|
|....(+).(3)..|
|..../.\......|
|..(5).(*)....|
|....../.\....|
|....(+).(4)..|
|..../.\......|
|..(1).(2)....|
|_____________|

Resulting Binary Tree

4.0 - Conclusion

Now , we'll start the postorder traversal as i mentioned earlier. We'll start from the lowest part of the binary tree. Post order traversal on "1,+,2" will give us, "12+" (left node, right node, root). So now, we replace the '+' node with 12+. We then consider the tree having left node 12+, right node 4 and root node *. It's postorder traversal will give us "12+4*" (again left node, right node , root node). So we replace * with "12+4*" and consider the tree with: left node "5", right node "12+4*" and root node "+".

Post order traversal will give you "512+4*+", so we again replace + node with "512+4*+" and consider the tree with: left node "512+4*+", right node "3" and root node "-". The final postorder traversal will give us "512+4*+3-" and thus, we've converted the infix expression to postfix expression using postorder traversal of binary trees.

5.0 - Recommended Resource:

http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html <--nice link to convert infix to postfix.