Home CPSC 340

Assignment 4 - Calculator

Due: March 20

Objective

To gain experience using stacks.

Task

For this assignment, you will write a program that implements a Reverse Polish Notation (RPN) calculator. RPN, also called postfix notation, is a system of writing mathematical expressions where the operator comes after the operands instead of in between. For example, we would normally write the seven plus two as:
7 + 2
In RPN, this would be written as:
7 2 +
We can combine multiple operations in RPN like so:
7 2 + 5 -
What this means is we apply + to 7 and 2 which gives us 9. Then we take the 9 and 5, then apply minus to those giving us 4. We can also have more than two numbers in a row:
1 2 3 4 + +

When we come to the first addition sign, we will add the previous two numbers, 3 and 4 to get 7. Next we will come to the second addition sign and add the previous two numbers. One is the 7 we just calculated and the other is the 2 we saw earlier. We then add these to get 9. When we get to the last addition sign, we will add the last two numbers: the 9 we just calculated and the original 1. Thus the final answer is 10.

One big advantage of RPN is that we no longer need to use parenthesis to specify the order of operations. For example the infix operations:

(1 + 2) * 3
and
1 + (2 * 3)
have different values. In RPN, the first one would be written as:
1 2 + 3 *
and the second would be:
1 2 3 * +

Another big advantage of RPN is that it can be more easily evaluated in a computer program. This is because we only need to scan left to right, instead of looking through the expression multiple times and following the order of precedence.

Your program will implement this task using a stack. To do this, you will scan through the RPN expression. Each time you see a number, you will push it onto the stack. When you see an operator you will pop two values off the stack, apply the operation to them, and push the result on the stack. At the end of the expression, the answer should be on top of the stack.

Your program will need to support these five operations:

If the stack is empty when you need to pop, or if the stack has more than one number at the end, or if you see input that's not a number, space or operator, then the expression was invalid, and you should report an error.

Your program should work on double-precision floating point numbers. Each line of input can consist of numbers, the five operators and spaces. Your program should keep evaluating expressions until the user enters an empty string.

A sample run of such a program can be seen here.


Details


Extra Credit

For extra credit, you may do either, or both, of the following:

General Requirements


Submitting

Submit your program by emailing your source files and makefile to ifinlay@umw.edu.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.