CptS 122 – Data Structures

Programming Assignment 4: Evaluation of Infix Expressions Using Stacks

Assigned: Monday, September 24, 2012

Due: Wednesday, October 03, 2012 by midnight

I. Learner Objectives:

At the conclusion of this programming assignment, participants should be able to:

• Design and implement a dynamic stack
• Allocate and de-allocate memory at runtime
• Manipulate links in a dynamic stack
• Insert items into a dynamic stack
• Delete items from a dynamic stack
• Traverse a dynamic stack

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

• Analyze a basic set of requirements for a problem
• Compose C language programs
• Create basic test cases for a program
• Apply arrays, strings, and pointers
• Summarize differences between array notation and pointer notation
• Apply pointer arithmetic
• Apply basic string handling library functions
• Define and implement structures in C
• Summarize the operations of a linked list
• Describe the operations of a stack including: push (), pop (), peek ()

III. Overview & Requirements:

Write a program to evaluate infix expressions. An infix expression looks like the following:

9 * (5 - 4) + 2 / 6

This program must first convert the infix expression to a postfix expression, and then evaluate the postfix expression. A postfix expression for the above infix expression looks like the following:

9 5 4 - * 2 6 / +

For this assignment you will need to implement and apply one stack to convert from infix to postfix, and implement and apply a second stack to evaluate the postfix expression. Your program must take the infix expression as a string from the user.

Please complete exercises 12.12 and 12.13 form your Deitel & Deitel C How to Program textbook. These exercises provide you with the algorithms required to perform the correct conversions and evaluations. Create a single program only, which combines both exercises. Also, be sure to allow the user to continue to enter infix expressions until they want to quit the program.

BONUS:

Provide appropriate test cases and drivers for each function in your stack application to receive up to 10 bonus points. For an additional 10 points allow for your program to accept multi-digit operands and unary sign operators (+ and -).

IV. Submitting Assignments:

1. Using the Angel tool https://lms.wsu.edu submit your assignment to your TA. You will "drop" your solution into the provided "Homework Submissions" Drop Box under the "Lessons" tab. You must upload your solutions as <your last name>_pa4.zip by the due date and time.
2. Your .zip file should contain a project workspace. Your project folder must have at least one header file (a .h file), two C source files (which must be .c files), and project workspace. Delete the debug folder before you zip your project folders.
3. Your project must build properly. 

V. Grading Guidelines:

This assignment is worth 120 points. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria:

1. 10 pts – Appropriate program driver, top-down stack design, style, and commenting according to class standards
2. 70 pts (5pts/function) – Correct stack function implementations
3. 20 pts – Correct usage of infix stack
4. 20 pts – Correct usage of postfix stack
5. BONUS: Up to 10 pts for correct test cases and drivers
6. BONUS: Up to 10 pts for multi-digit and sign operator implementation