Write a program that evaluates postfix arithmetic expressions containing real numbers and the operators +, -, *, and /. For more information on postfix notation see BACKGROUND below.
Input
The input is a series of arithmetic expressions in postfix notation read from a file. Each line in the file is a separate expression. Read the entire line from the file into an array of characters before processing. . The expressions are made up of operators (the characters '+', '-', '*', and '/') and real numbers. The end of the expression is marked by the expression terminator character, '='. Operators and operands must be terminated by at least one blank.
Real numbers must be expressed in decimal format: the whole part, followed by a decimal point ('.'), followed by the decimal part. The decimal point and the decimal part are optional. Exponential notation (that is, 3.2E3) is not valid.
The end of data in the file is marked with the character "#" instead of a new expression.
Output
After the evaluation of each expression, the results are printed to the screen:
"Expression = value"
where value is a real number in decimal format, .
Assumptions
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.
Sample Input: (RPN.TXT)
|
Sample Output:
|
For this project you must use Stacks as developed in Chapter 4, and you may use Sorted or Unsorted Lists from chapter 3. Projects may NOT use: arrays or strings except in the implementation of stacks or lists.
Grading for this project will be based on the following:
25 |
Design & Documentation, Including Test Set Design |
25 |
Code for "Postfix Evaluator" |
| 25 | Code for Stack, Sorted or Unsorted List Classes as needed |
25 |
Does It Work? |
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 - + * + * 56
4 2 + 3 5 1 - * + 18
Your task is to write a program that evaluates postfix expressions.
[1] Postfix notation is also known as reverse Polish notation (RPN), so named after the Polish logician, Jan Lukasiewicz (1875-1956) who developed it.