**Using
Stacks**

**Homework
#5**

*Postfix
notation ^{[1]}* is a notation for writing arithmetic
expressions in which the operands appear before their operators. There are no precedence
rules to learn, and parentheses are never needed. Because of this simplicity,
some popular hand-held calculators use postfix notation to avoid the
complications of the multiple parentheses required in nontrivial infix
expressions. You are to write a computer program that simulates how these
postfix calculators evaluate expressions.

In elementary school you
learned how to evaluate simple expressions that involve the basic binary
operators: addition, subtraction, multiplication, and division. (These are
called *binary* operators because they each operate on two operands.) It
is easy to see how a child would solve the following problem:

2 + 5 = ?

As expressions become more complicated, the pencil and paper solutions require a little more work. A number of tasks must be performed to solve the following problem:

(((13 - 1) / 2)((3
5))) = ?

These expressions are
written using a format known as *infix *notation. This same notation is
used for writing arithmetic expressions in C++. The operator in an infix
expression is written in between its operands. When an expression contains
multiple operators such as the one shown here, we need to use a set of rules to
determine which operation to carry out first. You learned in your mathematics
classes that multiplication is done before addition. You learned C++’s
operator-precedence rules in your first programming class. In both situations,
we use parentheses to override the normal ordering rules. It is easy to make a
mistake writing or interpreting an infix expression containing multiple nested
sets of parentheses.

* Postfix* notation is
another format for writing arithmetic expressions. In this notation, the
operator is written after the two operands.
Here are some simple postfix expressions and their results.

**Postfix Expression
Result**

4 5 + 9

9 3 / 3

17 8
- 9

The rules for evaluating postfix expressions with multiple operators are much simpler than those for evaluating infix expressions; simply evaluate the operations from left to right. Now, let’s look at a postfix expression containing two operators.

6 2 / 5 +

We evaluate the expression by
scanning from left to right. The first
item, 6, is an operand, so we go on. The
second item, 2, is also an operand, so again we continue. The third item is the division operator. We now apply this operator to the two
previous operands. Which of the two
saved operands is the divisor? The one
we saw most recently. We divide 6 by 2 and
substitute 3 back into the expression replacing

6
2 /. Our expression now looks
like this:

3 5 +

We continue our scanning. The next item is an operand, 5, so we go on. The next (and last) item is the operator +. We apply this operator to the two previous operands, obtaining a result of 8.

Here’s another example.

4 5 + 7 2 - *

Scanning from left to right, the first operator we encounter is +. Applying this to the two preceding operands, we obtain the expression

9 7 2 -
*

The next operator we encounter is -, so we subtract 2 from 7 obtaining

9 5
*

Finally, we apply the last operator, *, to its two preceding operands and obtain our final answer, 45.

Here are some more examples of postfix expressions containing multiple operators and the results of evaluating them. See if you get the same results when you evaluate them.

**Postfix Expression Result**

4 5 7 2 + - * -16

3 4 + 2 * 7 / 2

5 7 + 6 2 - *
48

4 2 3 5 1 - + * + 18

4 2 +
3 5 1 - * + 18

Your task is to write a program that evaluates postfix expressions entered interactively from the keyboard that adheres to the following specification. (The algorithm for converting from infix notation to postfix notation is in the next assignment.)

**Specification:
Program Postfix Evaluation**

The program evaluates postfix arithmetic expressions containing real numbers and the operators +, -, *, and /.

The input is a series of arithmetic expressions entered interactively from the keyboard in postfix notation. The user is prompted to enter an expression made up of operators (the characters '+', '-', '*', and '/') and numbers. You can assume that the numbers are one digit numbers for this lab (0-9). They must be read in as characters (because the operators are read in as characters), and converted to numbers. (EXTRA CREDIT: allow real numbers with multiple digits and decimals, such as 56.78) The end of the expression is marked by the expression terminator character, '='. Operators and operands must be terminated by at least one blank.

The user terminates the program by entering the character "#" instead of a new expression.

The user is prompted for each new expression to be evaluated with the following prompt:

"Enter expression to evaluate or a # to quit."

After the evaluation of each expression, the results are printed to the screen:

"Result = *value*"

where *value* is the result
of the postfix expression (a real number).

1. The expressions are correctly entered in postfix notation.

2. Each expression is terminated by '='.

3. The operations in expressions are valid at run time. This means that we do not try to divide by zero.

If we think about the postfix expressions, and how to evaluate them, we realize that when an operator is (the characters '+', '-', '*', and '/') is encountered, we apply it to the previous two operands (which have been read in, or are results of previous computation). For example, in the postfix expression:

6 2 / 5 +

we read the 6 and the 2 and then read the operand. The operand is applied to the two numbers. If we place numbers, or results of equations on a stack, then we can apply operations to the two top elements of the stack. In the expression above, we read a 6, and push it onto the stack. Then we read a 2 and push it onto the stack. We read the character '/', and apply it to the two top elements of the stack. 6/2 is 3 so we push 3 onto the stack. We read a 5 and push it onto the stack. When we read the final '+', we apply it to the two top elements of the stack (3 and 5).

¨ A listing of your program including any classes used

¨ A listing of the expressions that you used to test your program.

¨ A listing of the output file from the test runs

^{[1]}Postfix
notation is also known as reverse Polish notation (RPN), so named after the
Polish logician, Jan Lukasiewicz (1875-1956) who developed it.