CSci 131 -- Project 4

The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science
CSci 131 -- Algorithms and Data Structures I -- Spring 2001

Project #4
Due Date: start of class, Monday, April 9, 2001

In this project you will explore stacks and expression parsing. The project depends mostly on Chapters 6.1-6.5 and 7, but uses the linked-list material that you're already familiar with.

Part I.

Program 7.3 shows the specification of a generic package for LIFO stacks. Your task in this part is to change the private part of this package, and implement the body, such that a stack is represented as a linked list, not an array. Needless to say, you must also develop a test program that ensures that all the package operations behave properly.

Part II.

Program 7.16 (p. 305) is a bottom-up expression-parser function that converts an arithmetic expression into its RPN form. It does not handle parentheses, though. Your task in this part is to modify the program so parentheses are treated properly. Provide an interactive main program that prompts the user for an input expression, then produces and displays the corresponding RPN.

What to submit:

By now, you should be familiar with the various kinds of project elements, documents, etc. Submit those elements that are appropriate for this project.