Funtime CS lab.

The week, we wrote an infix-to-postfix expression translator. Not terribly easy, but very fun. The purpose of the translator is to provide an easy way to evaluate infix expressions, since to read postfix (RPN) is a much simpler task for a machine. The translator does its business by simply letting any operands pass through, but holding operators in a stack until a same- or lower-precedence operator is encountered. Here's an example: The expression "2 - 4 + 5 ^ 3 ^ 2" would first be tokenized into numbers and operators: {2, MINUS, 4, PLUS, 5, POWER, 3, POWER, 2}. The first token is a 2. It's a number, so it isn't touched; it becomes the first token of the result string. Then MINUS, since it's an operator, is pushed onto the stack. The 4 is passed through, making "2 4", then PLUS comes up. MINUS, the top of the operator stack, has the same precedence as PLUS, so we can pop it, giving us "2 4 -". The PLUS is pushed onto the stack, and the 5 after it makes "2 4 - 5". POWER is a higher operation than PLUS, though, so we just push it on top of PLUS. POWER, must be treated differently than PLUS or MINUS, because exponents evaluate from right to left, so we can't pop the first POWER before pushing the second. Finally, after the last token, 2, the string is "2 4 - 5 3 2", and the stack is {PLUS, POWER, POWER}, but now we've reached the end of the token list, so we need to pop the rest of the operators. This leaves us with "2 4 - 5 3 2 ^ ^ +", which is the proper postfix equivalent of the given expression "2 - 4 + 5 ^ 3 ^ 2", and it evaluates to 1953123. I didn't cover parentheses in that example, but they are relatively easy (although I had quite a time getting them to work): if you come across a closing parenthesis, pop operators until you find the opening one.

I hope that was a good refresher for those unfamiliar with RPN or stacks. Otherwise, learn to use an HP caluclator.