# Assignment 4 - Calculator

### Objective

To gain experience using stacks.

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:

• - subtraction
• * multiplication
• / division
• ^ exponentiation

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.

### Details

• You will need to have a stack to evaluate expressions. You should create a stack class split into in a header file (.h) and a source file (.cpp). You can base your stack off of an array or a linked list. Remember that the stack will have to store double-precision floating point numbers.
• You will also need to create another file for this program which will contain the main function of the program. This function will handle the input, and output as well as using the stack to perform each computation.
• You can assume that spaces will separate each number and operator in the input.
• You can assume that each line of input will be less than 100 characters.
• A function that may come in handy for input is atof. This function takes a string as a parameter and converts it into a double.
• In order to perform exponentiation, you can use the pow function. This takes two parameters, the base and the exponent and returns the result.
• Be sure to test your program thoroughly including the error cases.
• You will also need to write a makefile for compiling your program. You can look at the makefiles provided in previous assignments, and review the lab on makefiles in order to write your own.

### Extra Credit

For extra credit, you may do either, or both, of the following:
• Add support for symbolic constants PI and E which evaluate to their values:
2.5 PI + E *

• Add support for a "SQRT" operator that replaces the top of the stack with its square root:
64 SQRT


### General Requirements

• No global variables other than constants.
• All member data of a class must be private.