CSCE 2014 - Homework 3 and 4
Homework 3 Due - 03/17/2011 at 11:59 PM
Homework 4 Due - 04/01/2011 at 11:59 PM

1. Problem Statement:

The goal of this programming project is to implement a postfix calculator that allows the user to define and reuse variables in their calculations. For example, if the user types in "A = 2 3 +" the value 5 will be stored in variable A. If they then type in "B = A 6 *" the value 30 will be stored in B.

To accomplish this task, students must use a linked list to create a symbol table that contains the current value of all variables that have been defined, and they must use a stack of floating point values to evaluate the postfix expression. Since this is a large and complex project, it will be broken into two parts as described below.

2. Design:

Homework 3: Symbol Table Creation

In order to use variables in our calculator, we need some way to store the names of variables as they are defined, and keep track of their current values. A linked list is ideal for this purpose, because it can grow in size as variables are defined, and linked list methods can be used write/read the values associated with each variable.

To implement/test your symbol table, start with the sample linked list code list.h and list.cpp. You will see that this list class contains one string and one integer, and methods to Insert, Search, Delete, and Print the list. Your first job is to modify this class to store floats instead of integers.

Your next job is to extend the main program to allow users to type in commands of the form "variable = number", and store these values in the symbol table. For example, if a user type in "A = 2.81" and then "A = 3.14", then the linked list should contain one node with (A, 3.14) in it. It should not contain two nodes with A values.

Your final job is to implement a command that allows the user to print out the current values of all variables in the symbol table. The easiest way to do this is check for a special symbol like "?", and print the contents of the linked list when it is found.

Once you have completed the symbol table creation, upload your source code as "hw3" on (or before) the due date.

Homework 4: Postfix Expression Evaluation

Postfix expressions were used in early HP calculators because the syntax is very easy to evaluate (even though it looks strange). The idea is that whenever a number is entered, it is pushed onto the stack, and whenever an operator (+, -, *, /) is entered, the top two values are popped off the stack, and the value of "num1 op num2" is pushed back onto the stack.

For example, if the user types "A = 2 3 +", the values 2 and 3 are pushed onto the stack, and when the "+" is read they are popped off and the sum 5 is stored on the stack. Since this is the last token in the expression, the stack is popped one last time and the value 5 is stored in the variable A. Similarly, if the user then types in "B = A 2 *" then the value of A is looked up in the symbol table, and 5 and 2 are pushed on the stack. Then when "*" is read these two numbers are popped and their product 10 is pushed on the stack and popped off and stored in variable B.

The situation for - and / operators is more complex because the ordering of the values makes a huge difference; "2 - 7" and "7 - 2" have opposite signs. The convention most people use is that the ordering of values in the postfix expression should be the same as the ordering in the postfix expression. For example, "8 2 /" should be interpreted as "8 / 2".

You have seen a partial stack implementation in lab#7. A more complete stack class can be found in stack.h and stack.cpp. You will see that this stack class contains one string and one integer, and methods to Push, Pop, and Print values in the stack. Your first job is to modify this class to store floats instead of integers. Then you can use the stack in your main program to evaluate postfix expressions when they are entered by the user.

Once you have completed your fancy postfix calculator, upload your source code as "hw4" on (or before) the due date.

3. Implementation:

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.

4. Testing:

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. Try your program on 2-3 input documents, and save your testing output in text files for submission on the program due date.

5. Documentation:

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.

6. Project Submission:

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.

You should also PRINT a copy of these files and hand them into your teaching assistant within ONE DAY of the due date. This can be done during class, during lab, or using the department mailbox. Attach a copy of the Programming Project Evaluation Form to your report with your name and project number filled in.