11.14. Homework 14 - RPN CalculatorΒΆ
Write a program that works as a simple RPN (Reverse Polish Notation) calculator. RPN calculators work slightly different than normal calculators. Because they work on the model of a stack, it is never necessary to use parenthesis to express a mathematical equation, regardless of how complex the equation is. Many scientists, mathematicians and engineers consider RPN to be a much better model for using a calculator than the more common calculator model, which uses parenthesis and equal signs.
The main concept to understand about how RPN calculators work is that they use a stack (last in, first out) and postfix binomial operators. As new data is entered, it is pushed onto the top of the stack, pushing the previously entered data further down the stack. Binomial operators are entered in postfix manner after the two numbers have been entered. When an operator value is entered, the top two values on the stack are used to determine a result, which is stored at the top of stack.
To add the numbers 4 and 5 to get a sum of 9, with an infix calculator, one would enter:
4 + 5 =
On an RPN calculator, this would be expressed as:
4 [enter] 5 +
When the [enter] key is pressed, the 4 is pushed onto the stack. The 5 is then put at the top of the stack. When the calculator processes the +, it takes the top two stack values (4 and 5) adds them together and stores a 9 at the top of the stack. Whatever is the top stack value is what is displayed on the screen.
Note
For the input of a computer to work exactly like a real calculator, the input would need to be processed in raw mode rather than the normal buffered, also called cooked, mode. We will not tackle that complexity for this problem, so for the above example, the keys pressed on the keyboard would need to be as follows:
4 [enter] 5 [enter] + [enter]
Data should be read from the keyboard as strings. If the data entered is one of { +, -, *, /}, then the operation of add, subtract, multiply or divide should be performed on the top two stack values with the result being stored to the stack. Entered numeric data should be pushed onto the stack as a floating point number. If the user presses the enter key without entering any data, then the program should push the top stack value onto the stack again (top two stack values are the same). Any other data (e.g., text characters), should be treated as a user error with an error message displayed. The special sentinel key of a grave accent ` should be used to cause the program to exit.
The stack should be implemented using a linked list. Depending on your implementation, you may wish to implement the following functions before you can really begin implementing the calculator.
| Function | Use |
|---|---|
| void *push( Stack *, double ); | Add a number to the top of the stack |
| double pop( Stack * ); | Return and remove the top stack item |
| double get( Stack * ); | Return the top stack item |
| void replace(Stack *, double); | Replace the top stack value |
| void show( Stack * ); | Display the top stack value |
Based on code in the study guide, here is some code to get you started
working with a stack. stack.c
Hint
- Use the ReadLine function to reliably read in the data. (String Example - ReadLine)
- You will want a fixed variable in
mainto hold a pointer the first node of the stack. Since you will need to update this pointer from within functionspushandpop, they will need the memory address of this pointer (pointer to pointer). - See Example Use of strtod and strtol. You will want to use this example function to convert the string data to doubles and to determine if numeric data was entered or not.
