Help understanding Reverse Polish Notation for homework assignment?

Question

I have been asked to write a simple Reverse Polish Notation calculator in C as part of a homework assignment. I'm having difficulty understanding RPN. Can you please help me understand Reverse Polish Notation? Also, any tips on how to approach this problem would be greatly appreciated.

Answer 1

You can find the tutorial at http://www.codeproject.com/KB/cs/Reverse_Polish_Notation.aspx

Answer 2

Reverse Polish Notation is a form of notation for mathematical expressions where the operators follow the operands. When evaluating an RPN expression, each binary operator refers to the two operands immediately preceding it. Take this RPN expression for example:

5 4 3 + *

Start scanning the expression from the left until you come to the first operator, which is +. This operator has the operands 4 and 3 (the ones that come immediately before it), so we can replace all three with the result, 7. (Note that the parentheses aren't necessary, but I'm using them to help clarify the meaning).

5 (4 3 +) * => 5 7 *

Now we have the operator *, and the two operands 5 and 7 (which is really the result of 4 + 3). We multiply 5 and 7 and the whole expression evaluates to 35.

5 7 * => 35

This is the general algorithm for evaluating any RPN expression.

---

RPN expressions are particularly well suited for evaulation by computers using a data structure known as a stack.

A stack is an ordered collection, where one end is designated the "top". Items are always added to the stack or removed from the stack at the top. This way, the only item to remove is always the item that was added most recently. For this reason, stacks are sometimes referred to as Last In, First Out (or LIFO), because the last element pushed onto the stack is on the top, and thus will be the first to be removed.

In C, you could implement a stack with two variables: an array (large enough to hold the maximum number of elements you expect the stack to ever need) and an integer which indicates which index in the array is currently the top.

Stacks are well suited for evaluating an RPN expression because when you encounter an operator, it always applies to the most recently encountered operands. So as you scan the expression from the left, you can save the operands on a stack. Take our example again:

5 4 3 + *

The first thing here is an operand (5), so push it onto a stack (which is initially empty). Then we encounter 4 and push it on the stack as well. It becomes the new top. Then we do the same with 3.

5 4 3 <-- top
+ * // Remaining expression

Next we encounter the + operator. We know it applies to the previously encountered operands, but where do we find them? On top of the stack, of course! Pop 3 and 4 from the stack and add them to get 7. But what to do with the result? Well, it could be the operand to another operator, so push it back on the stack (just like we replaced the operands and operator with the result when we evaluated the expression by hand):

5 7 <-- top
* // Remaining expression

Now we see *. Once again, the most recently encountered operands are the two top operands on the stack. We pop them and multiply to get 35, then push it back on the stack.

35 <-- top
// No expression remaining

At this point, we've reached the end of the expression and the only thing on the stack is the result. We're done! You can see how the operand stack "saves" the first operands encountered until the corresponding operator is encountered, which could be on the other end of the expression.

If we'd reached the end and found that there was more than one number left on the stack, that would have told us that there were too many operands in the expression and not enough operators. On the other hand, if we had encountered an operator at some point and had fewer than two operands on the stack, we would know there were too many operators and not enough operands in the expression.

Answer 3

You can find a simple implementation at http://expressionoasis.vedantatree.com/