Read the sections in their entirety before you start programming
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.
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.
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
method in postfix_calculator
to_string
method of postfix_calculator
This last may be helpful to you as you test your program.
Code compiles and runs: | 5 points |
README | 5 points |
Code style | 5 points |
Inputs values and stores them on the stack correctly (tested using the debug command) |
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 |
Submit a zip file on Canvas containing:
The README file is just a plain text file (usually named README or README.txt). Your README must contain the following: