UCR CS 14: Introduction to Data Structures and Algorithms
Spring Quarter 2003 /
Class webpage
Assignment 03: Stacks
Remember:
- All programming assignments will be done under the Linux operating system, using standard programming tools for that environment.
- All programming assignments will be evaluated with the -Wall -Werror compilation options. If your program does not compile with these flags, it will not be evaluated.
- Concentrate some effort on style and documentation. A significant portion of your grade will be based on these aspects of your submission.
Chapter 6* introduced the ADT stack:
'The term "stack" is intended to conjure up visions of things encountered in daily life, such as a stack of dishes in the school cafeteria, a stack of books on your desk, or a stack of assignments waiting for you to work on them. To computer scientists, however, a stack is not just any old pile. A stack has the property that the last item placed on the stack will be the first item removed.'
Figure 1 illustrates the pseudocode of the operations for the ADT stack. Figure 2 shows the UML diagram for the class Stack.
// StackItemType is the type of the items stored in the stack
+createStack()
// Creates an empty stack.
+destroyStack ()
// Destroys a stack.
+isEmpty():boolean { query }
// Determines whether a stack is empty.
+push(in newItem:StackItemType) throw StackExpection
// Adds newItem to the top of a stack.
// Throws STackException if the insertion is not successful.
+pop() throw StackExpection
// Removes the top of a stack; that is, removes the item
// that was added most recently.
// Throws STackException if the deletion is not successful.
+pop(out stackTop:StackItemType) throw StackExpection
// Retrieves into stackTop and then removes the top of a
// stack. That is, retrieves and removes the item that was
// added most recently.
// Throws STackException if the deletion is not successful.
+getTop(out stackTop:StackItemType) {query}throw StackExpection
// Retrieves into stackTop the top of a stack. That is,
// retrieves the item that was added most recently.
// Retrieval does not change the stack.
// Throws StackException if the retrieval is not successful.
|
Figure 1. Pseudocode for the ADT Stack Operations (page 277*)
Figure 2. UML diagram for the class Stack
* CARRANO, F.M., PRICHARD, J.J. Data Abstraction and Problem Solving with C++. 3rd edition, Addison Wesley, 2002.
The Assignment (10 points)
7 points. Write an implementation of the ADT stack that uses a linked list to represent the stack items. So, you will have two files: Stack.h (header) and Stack.cc (implementation).
3 points. Write a main program (stacks.cc) that checks for balanced curly braces { }, square brackets [ ], and parenthesis (), using one (only one) Stack. Braces may not be interleaved. For example, you may not have the following sequence of braces: { [ ( ) } ]. Note that in this example {} and [] are interleaved. Your program will receive a file as input, check if this file has balanced braces, and prompt either of these two messages:
- Braces are balanced.
- Braces are not balanced: explanation
Note that you have to give an explanation why the braces are not balanced. For example:
INPUT FILE CONTENT
|
OUTPUT
|
|
{ [ real
( simple
) effective
] example } 1
|
Braces are balanced |
|
{ real
( simple
) effective
} example
[ 2 ]
|
Braces are balanced |
|
{ [ real
( simple
) effective example
} 3
]
|
Braces are not balanced: missing ] before } |
|
( ( real
( simple
) effective
) example
) )
(5)
|
Braces are not balanced: missing (
or
Braces are not balanced: extra ) |
Bonus Credit
- (3 points more) Add to your explanation the position of the wrong symbol (the position in which you notice there is an error). For example:
{ [ real
( simple ) effective example } 6
Braces are not balanced: missing ] before }, file line 2 string column 31.
Braces are not balanced: missing ] before }, symbol 5.
Braces are not balanced: missing ] before }, curly brace 2.
About bonus credit. This part of your work has two main purposes:
1. Let you use and test the data structure you have defined in an application.
2. Give you a chance to increase your grade. If you already have an A, this may help you to add a beautiful A+ in your records.
Hints and considerations