A way of doing math
. Normal people do math in infix
notation, which results in problems with operator precedence
and introduces the need for parentheses
. Here are some examples of infix notation:
(2 + 3 ) * 5
((4 -2) + (3 * 2))
3 + (2 - ((6 / 3) * 2))
Here are the same examples in postfix notation. Note the lack of parentheses:
2 3 + 5 *
4 2 - 3 2 * +
3 2 6 3 / 2 * - +
This is how reverse polish notation calculators work. Postfix also allows you to write a stack calculator in about two shits. Every time you see a number, push it onto the stack. Every time you see an operator, pop twice, operate on the two numbers, and push the result back on. Just work the input stream left to right and you'll get it.
So, how would we solve "2 3 + 5 *" using a stack? Look at the first part of the expression. It's a number. So we push it onto the stack. The next part is another number. Push it onto the stack as well. Then the next part is an operator (a + sign). So we pop twice, do the operation, and push the result back on. Our stack looked like this before the operation:
So we'd pop off a 3, then pop off a 2. Add the two numbers and push the result back on. The stack now contains only a 5. Now, look at the next part of the expression. It's another number. Push it on the stack as well. The stack is now two fives. The last part of the expression is a multiplication sign. Pop off the two fives, multiply, and push the result back on. The stack now only contains a 25, which is the answer. Compare that to the result from the infix version. And we got to the answer without order of operations, because we could use a stack.
We can convert between infix and postfix very easily using a binary tree. Just make a tree out of the expression, where the nodes are the operators and the leaves are numbers. A tree for the above example would look like this:
The algorithm used to write down a postfix version of that tree goes like so (transferring this to code should take no time at all):
- Go to the left node and recurse.
- Go to the right node and recurse.
- Write down the number or symbol at the current node.
With a program like lex or flex, you can do postfix arithmetic so fast it's not even funny. Many people would say that postfix is much faster and easier. I would agree. Compare to prefix notation.