Assignment 1 -Evaluating a Postfix Expression- Due 9/14

One common application of a stack to find the value of a postfix expression. First, let's explain the terminology. An infix expression is the type that we are used to in ordinary algebra, such as 3 + 9, which is an expression representing the sum of 3 and 9. Infix expressions place their (binary) operators between the two values to which they apply. In the above example, the addition operator was placed between the 3 and the 9.

A postfix expression, in contrast, places each operator after the two values to which it applies. (Post means "after", right?) The above expression would be 3 9 +, when rewritten in postfix. Here are a few more examples in the following table. The infix form is shown on the left, and the postfix form is given on the right.

Infix:	Postfix:
16 / 2	16 2 /
(2 + 14) * 5	2 14 + 5 *
2 + 14 * 5	2 14 5 * +
(6 - 2) * (5 + 4)	6 2 - 5 4 + *

Note that postfix expressions do not use parentheses for grouping; it is not needed! Infix sometimes requires parentheses to force a certain order of evaluation. For example, in the second example above, parentheses were needed to indicate that the addition should be done before the multiplication. Without the parentheses you get the third example, where the multiplication is done before the addition (using the precedence rules from ordinary arithmetic, or from C++, for that matter).

Arithmetic expressions like the above can of course be much longer. We could also allow other operators, such as ^ for exponentiation, or perhaps a unary minus. A sample infix expression that uses exponentiation is 4 ^ 2, which means 4 to the second power. A unary minus is sometimes used as in the infix expression -(4 + 2). A unary operator is one that is applied to a single value, as opposed to the typical binary operators, which are applied to two values. We will not consider unary operators or exponentiation further here.

The algorithm to evaluate a postfix expression works like this: Start with an empty stack of integers. Scan the postfix expression from left to right. Whenever you reach a number, push it onto the stack. Whenever you reach an operator (call it Op perhaps), pop two items, say First and Second, and then push the value obtained using Second Op First. When you reach the end of the postfix expression, pop a value from the stack. That value should be the correct answer, and the stack should now be empty. (If the stack is not empty, the expression was not a correct postfix expression.)

Let's look at the postfix expression evaluation algorithm by way of example. Consider the postfix expression 2 14 + 5 * that was mentioned above. We already know from its infix form, (2 + 14) * 5, that the value should be 16 * 5 = 80. The following sequence of pictures depicts the operation of the algorithm on this example. Read through the pictures from left to right.

Let's evaluate another postfix expression, say 2 10 + 9 9 - /, which is (2 + 10) / (9 - 6) in infix. Clearly the value should work out to be 12 / 3 = 4. Trace through the algorithm by reading the following pictures from left to right.

When one reaches an operator in this algorithm, it is important to get the order right for the values to which it applies. The second item popped off should go in front of the operator, while the first one popped off goes after the operator. You can easily see that with subtraction and division the order does matter.

Assignment: Develop a C++ program that repeatedly evaluates postfix “integer” expressions with the 4 operators “+, -, /. *”. Where “/” is integer division. It should print out the current value at the top of the stack when encountering a “p” and quit when encountering a “q”.

Hints:

1. You may use the standard library container <stack> with its methods top, pop, and push.
2. When using the stream extraction operator >> with cin (cin >> c) you may extract a character determine whether it is an operator or a digit if it is a digit you may use cin.pushback(c) to put the character back in the stream then use >> to read an integer.
3. The calculator class should be able to
1. store (push) an operand,
2. read and pop the top two operands then do an operation on them and store the result
3. printout the current top value

Xtra credit check for input errors and handle exceptions.