The goal of this programming project is to write a C++ program that reads and evaluates simple "prefix expressions". This notation was invented in the 1920's by the Polish logician Jan Lukasiewicz so it is often called "Polish notation". With this notation we write the operators BEFORE the two arguments in an expression. Hence "2 + 3" becomes "+ 2 3". More complicated expressions may have series of operators followed by several arguments. For example, "2 + 3 * 4 - 6" would become "+ 2 - * 3 4 6".
In order to calculate the value of a "prefix expression" we must REVERSE the order of the tokens in the input string to create the corresponding "postfix expression" (postfix expression format is also known as "reverse Polish notation" for obvious reasons). To do this, you need to create a stack that can store strings, and use this stack to reverse the user's input. To evaluate the postfix expression, you need to create a stack of floats, and perform the stack-based postfix evaluation described in class and in the book.
Your expression evaluator must be able to handle '+', '-', '*' and '/' operations. To simplify the I/O processing, we will use an '=' character at the end of the prefix expression to mark the end of the user's input. This way, when the user types in "* 7 8 =" your program will push the strings "*", "7", "8" onto the stack, and then pop them off to get the postfix expression "8 7 *" that must be evaluated using the floating point stack. You can call the function "atof" in the cstdlib library to convert strings like "3.14" into floats.
There are two sample implementations of stacks in the source code directory that you can adapt for this project. There are also two implementations of postfix calculators that you can use. The postfix calculators handle many operations that you are NOT required to implement (e.g. sqrt, pow, abs) so you will only need a small portion of this code.
With expression evaluation, there are many things that can go wrong if the user types in something wrong, or if the calculation is impossible. Think about the list of all possible errors, and test your program with 2-3 incorrect input strings. For each input string, document what your program does. For example, what happens if the user types in "= + 1 2 3"? I am expecting your program to catch 1-2 of these potential errors, but you do not need to catch every possible user mistake. Just be sure to document which cases you do handle, and which cases you do not handle.
You can implement this program using either a bottom-up approach or a top-down approach. If you go for a bottom-up approach, start by creating basic methods and classes, and test theses methods using a simple main program that calls each method. When this is working, you can create the main program that uses these methods to solve the problem above.
If you go for a top-down approach, start by creating your main program that reads user input, and calls empty methods to pretend to solve the problem. Then add in the code for these methods one at a time. This way, you will get an idea of how the whole program will work before you dive into the details of implementing each method and class.
Regardless of which technique you choose to use, you should develop your code incrementally adding code, compiling, debugging, a little bit at a time. This way, you always have a program that "does something" even if it is not complete.
Test your program to check that it operates correctly for all of the requirements listed above. Also check for the error handling capabilities of the code. Test your program and save your testing output in text files for submission on the program due date.
When you have completed your C++ program, write a short report (less than one page long) describing what the objectives were, what you did, and the status of the program. Does it work properly for all test cases? Are there any known problems? Save this report in a separate text file to be submitted electronically.
In this class, we will be using electronic project submission to make sure that all students hand their programming projects and labs on time, and to perform automatic analysis of all programs that are submitted. When you have completed the tasks above go to the class web site to "submit" your documentation, C++ program, and testing files.
The dates on your electronic submission will be used to verify that you met the due date above. All late projects will receive reduced credit (50% off if less than 24 hours late, no credit if more than 24 hours late), so hand in your best effort on the due date.