Calculator

In this assignment you will implement a simple Reverse Polish Notation calculator using a simple "stack". This calculator supports only integer arithmetic and the four basic operations (addition, subtraction, multiplication, integer division).

Recall that an RPN (Reverse Polish Notation) calculator is one which does not use parenthesis nor an equal sign. It's the standard adopted by most Hewlett Packard calculators, so if you have one of those, you'll feel right at home.

Let's start with an example: suppose you want to compute the result of 
(2 - 3) * (2 + 3 * (5 + 3) / 4)
How would a person do it? We all do it by evaluating the innermost parentheizied expressions first. In this case, there are two parenthesized expressions of "equal importance:" the (2 - 3) at the beginning and the (5 + 3). Either one of these can be evaluated first without contradicting the operator precedence rules of arithmetic: multiplication and division before addition and subtraction, unless you use parenthesis to force addition and subtraction to be executed first.

An RPN calculator evaluates the sample expression above the say way a human does, but it's up to the human to enter the sub-expressions in the correct order. In other words, an RPN calculator will not parse the expression. You have to parse it yourself to figure out what to evaluate first. Thus, if I were to use my 21-year-old HP 41 CV to compute the sample expression above, I'd have to punch 2, 3, -, 5, 3, +, 4, /, 3, *, 2, +, *, in that order, separated by presses of the ENTER key.

Now, how does my HP 41 CV know what to do with those numbers and operations? How are then stored? The answer to all these questions lies in the use of a stack.

I covered stacks in handout 2 and will be covering them again in more detail in lecture. Here, I'll just use one to show how the sample expression above is evaluated.

If you refer to the figure at right, you'll see that every time I enter a number, that number is pushed onto the top of the stack. What may be a little confusing at first is what happens when I enter one of the operations. What happens in that case is that the stack is popped twice, to retrieve the numbers to operate on, then the operation is performed on them, and finally the result is pushed back onto the top of the stack. As a result, it looks as though the stack was popped only once. As the saying goes, looks can be deceiving.

Now you're ready to tackle your programming project. Your task is to write a C++ program which (a) uses an array (of fixed size) to implement a stack and, using that, (b) simulates an RPN calculator. Don't worry about implementing anything but the four arithmetic operations (+, -, *, /), on integers only. Ignore the problem of integer division. If you have to divide 2 by 5, for example, go ahead and let it return 0. You should be careful, however, to recognize the situations when the stack is empty or when it's full. You don't want to pop from an empty stack or push onto a full stack; it's not good for your health.

In addition, your program must output the entire array after every input. Here's the actual output of my own solution to this problem (with an array of size 3) when I tried to evaluate the expression 2 * (3 + 5) by entering 2, 3, 5, +, *, - in that order: 

Hello... I simulate a simple RPN calculator.
Would you like to try me? [y/n] y

Please enter the expression you want to evaluate,
one number or operation per line.

2
        0
        0
        2 <--- top
3
        0
        3 <--- top
        2
5
The stack is now full.
        5 <--- top
        3
        2
+
        5
        8 <--- top
        2
*
        5
        8
        16 <--- top
-
The stack is empty. Cannot continue.
Notice that I entered an extra - after the expression was evaluated. That was obviously a mistake (intentional, so that I could explain it here) and the program caught it by printing a `stack empty' error. What happened, of course, was that after the expression was evaluated completely, only a single item was available on the stack (namely, 16, the result). Thus, as the program tried to perform the - operation, it tried to pop the stack twice. The first time was fine (the 16 was popped), but now the stack was empty and couldn't be popped again.

Your program should perform error checking in a fashion similar to mine. It should detect when the stack is full or empty and should print an error message and exit when an attempt is made to push onto the stack if it's full or pop from it when it's empty. It should also print the array as I did, indented so as to make it easy to read, and it should indicate the top of the stack as I did.

In the example above, I used an array of size 3. Your program should use an array of size 5, instead. It should be written in a modular fashion, namely, with functions performing groups of related actions, instead of having one large main(). Remember to name your variables and functions appropriately and to use the coding standards posted on the course web page. Finally, at the end of this assignment you'll find a piece of code for everyone to use (it's available on its own to download from the course web page so you don't need to type it yourself). It contains the error codes I defined and it also shows the function that parses the input to find out if the input is an operator (+, -, *, /) or a number (positive or negative). It's not perfect, (If you enter 5- together, it will interpret the input as negative 5, but 5+ gives you an error. If you enter +5, it also gives you an error.) but it suffices for this task. This function calls on two other functions to return its result: You must implement these functions, for they are the ones which really do the job.

Starting Code

You may download this as a starting point: calc.cc

Hints