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.