Postfix

(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:

2 3

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:

     *
    / \
   +   5
  / \
 2   3

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):

1. Go to the left node and recurse.
2. Go to the right node and recurse.
3. 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.

Like qmail, Postfix is an MTA attempting to replace sendmail which is showing its age in the form of security problems among other things. From their Web site (www.postfix.org): ``Postfix attempts to be fast, easy to administer, and hopefully secure, while at the same time being sendmail compatible enough to not upset your users.'' Incidently, I'm a relative Unix newbie, and Postfix is the only MTA I found remotely easy to configure.

Keep track of what node you are in in your tree. This means nodes are going to have to have a parent element.

• ( - insert a '(', then go downleft one node. Do not include this when you go back for reading the RPN expression.
• ) - recurse up the tree until the node you are on is a '('.
• +, -, *, / - recurse up until you are at a node who's parent is an operator of higher precedence, then move the node at the current location down and to the left (without chaning the current location), insert the operator at current location, then move the current location down and to the right.
• A number - insert at current location.

To get out the RPN expression, just read the tree in postorder.

Precedence table (a.k.a. order of operations):

1. Parentheses
2. Multiplication and division (read left to right)
3. Addition and subtraction (read left to right)

If you add modulus (%), put that in with multiplication and division. If you add exponents (^), put it between parentheses and multiplication/divison.

Post"fix (?), n.; pl. Postfixes (#). [Pref. post- + -fix, as in prefix: cf. F. postfixe.] Gram.

A letter, syllable, or word, added to the end of another word; a suffix.

Parkhurst.

© Webster 1913.

Post*fix" (?), v. t.

To annex; specifically Gram., to add or annex, as a letter, syllable, or word, to the end of another or principal word; to suffix.

Parkhurst.

© Webster 1913.