Description
Purpose
-
To practice working with stacks
-
To build a cool and useful command line calculator
Before You Begin
-
Read the sections in their entirety before you start programming
Introduction
You will be implementing a calculator which uses reverse Polish notation (RPN), also known as postfix notation. In postfix notation, operators come after the operands. An example of RPN to add two numbers is
4 6 +
which evaluates to 10. You can make more complex expressions combining various operations:
10 2 / 4 +
is equivalent to (10 / 2) + 4. Note that parentheses are never used in RPN, nor is operator precedence considered in evaluating RPN expressions. Operations are applied left-to-right; each binary operation uses the two nearest preceding values as operands; the operands and the operator are then replaced by the result of the operation. In the above expression, the / operator acts first, on 10 and 2, resulting in a 5. The + operator then adds 5 and 4 to get 9. Here’s another way to get the same result:
4 10 2 / +
In this case, the / again operates first on the 10 and 2, leaving a 5. The + now acts on 4 and 5 to get 9. Note how RPN evaluations implicitly use a stack; numbers are pushed onto the stack, while binary operators pop two numbers off the stack and push one number (the result of the operation) back onto the stack.
Order is important; the expression
10 2 /
evaluates to 5, while
2 10 /
would be 0.2. Similarly,
6 5 –
evaluates to 1, not -1.
For more, read the wikipedia article.
Outline
You will be implementing the class postfix_calculator. If you look at the provided postfix_calculator.h, you will see that the class (as written) defines a number of member functions, which you must implement.
The most crucial is the evaluate method, which takes in an expression in RPN and evaluates it, leaving the answer on the stack. The evaluate method must also report any errors which occur in the evaluation of the expression. If there is an error, evaluate returns false, otherwise it returns true. Note that in your calculator, it is not considered an error to have extra items left on the stack; this allows for partial evaluation of expressions. Answers are also left on the stack, allowing for continuations of calculations. For example, it is legal to do
7 3 *
obtaining the answer 21, then follow with
6 –
which will use the 21 from the previous result and give 15.
Other functions include clear, which empties the stack, and top, which returns the top item on the stack (which should be the answer from the most recent evaluate call). There is also a to_string method which can be used for debugging.
Note that you will need to create member variables to hold your stack and possibly other things. You may go about this any way you want. Be sure to initialize things properly in your constructor.
For full credit, your calculator must properly evaluate RPN expressions, of any length, using the four primary binary operators (+, -, * and /). All values should be input, output, and evaluated as doubles.
Here are some samples to test your completed calculator on (correct answers in parentheses):
10.0 2.0 / 4.0 * 6.0 – (answer: 14)
10 2 4 6 – / * (answer: -10)
10 3 2 + / 17 – -2 * (answer: 30)
Of course, we will test on more than this – be sure to thoroughly test your calculator yourself!
For extra credit, also implement the binary exponentiation operator (^), and the unary operators for square root (sqrt), base 10 logarithm (log), natural logarithm (ln), and the trigonometric functions sine (sin), cosine (cos) and tangent (tan). Unary expressions in postfix work just like binary expressions except that they pop only one number off the stack. Examples:
2 3 ^ (answer: 8)
4 sqrt (answer: 2)
3.14159 2 / sin (answer: 1)
Finally, feel free to add interesting features of your own design. Document these in your README, so we know to look for them. If we feel they merit it, you can earn an additional 3 points of extra credit.
Technical Details:
A substantial amount of code has been written for you, which can befound in:
The calculator_main.cpp file contains the main function and does all of the user interface work for you. You may modify calculator_main.cpp for your own testing purposes; however, the final version of your code has to work correctly with the unmodified calculator_main.cpp.
As previously described, you need to implement several methods in postfix_calculator.cpp; these will have TODO comments. You may define and implement any other functions as needed in postfix_calculator.h and postfix_calculator.cpp.
For the extra credit, you will find the functions you need in the <cmath> standard library.
Finally, note that calculator interface (as provided) supports three special commands:
-
clear – calls the
clearmethod inpostfix_calculator -
quit – exits the program
-
debug – prints the current stack contents using the
to_stringmethod ofpostfix_calculator
This last may be helpful to you as you test your program.
Grading:
|
Code compiles and runs: |
5 points |
|
README |
5 points |
|
Code style |
5 points |
|
Inputs values and stores them on the stack correctly |
10 points |
|
Correctly handles simple binary expressions such as 10 2.5 / and 4 7 + |
20 points |
|
Correctly handles more complex expressions such as 5 1 2 + 0.5 * + 3 – |
20 points |
|
Total: |
65 points |
|
Extra credit: implementation of ^, sqrt, log, ln, sin, tan, and cos. |
1/2 point each |
|
Extra credit: innovations of your own design |
Up to 3 points |
Submission Instructions:
Submit a zip file on Canvas containing:
-
README
-
All of your source code (include the Makefile and calculator_main.cpp)
The README file is just a plain text file (usually named README or README.txt). Your README must contain the following:
-
Include names of all people who helped/collaborated as per the syllabus
-
Describe the challenges you encountered and how you surmounted them
-
What did you like/dislike about the assignment?
-
How long did you spend on this assignment?
-
A description of any novel features you added for extra credit
