Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 3
Due Wednesday, February 16, 2000.

-
Goals of this assignment:
-
To understand the use of a stack
to hold references to unfulfilled obligations, and to gain
experience in using a stack.
-
To understand the concept of separating the use of an abstract
data type from the implementation of that abstract data type,
and to gain experience in implementing that separation, using hiding
and user interfacing.
-
It is expected that students will discuss the assignments. But do
not turn in code written by another person. If that happens, both
persons are violating the ethics of this course. Representing the
work of another person as your own is plagiarism, and may result in
a disciplinary "F" in the course.
It is permissable (in this course, as this is up to the instructor)
for you to obtain ideas from other students or from other persons.
But you must type in the code yourself.
It is unadvisable for you to allow another student to have an electronic
copy of your work, as then you would unwittingly be a party to a breach
of these rules. Showing the other student a hard copy is less dangerous.
The above rule does not apply to copying files that I have made publicly
available. I expect that you will use those in their original form or
with appropriate modifications (made by just you, of course).
If you utilize code that you obtain from other sources, be sure to give
credit in a comment, such as:
// this code from website www.mit.edu/help/x13
-
Write a stack-based algorithm which evaluates an arithmetic expression
which uses only the operators for addition, subtraction, multiplcation,
negation (that is, unary "-"), and integer division, and uses only integer
constants written in base 10 notation. Parentheses may also be used.
It is optional for you to allow the "mod" operator.
The standard operator precedence of C++ is to be used. That is, the
unary minus operator has precedence over the multiplicative operators,
which have precedence over the binary additive operators.
-
Your program should take as input a line of text such as:
103-(56+3*(-2))+12*10/15
Your program must read the input one symbol at a time. (For example, it reads
first "1" then "0" then "3" then "-" etc.) Do not use the built-in facility
for reading integers.
It is optional for you to write the program to allow spaces in the input
line. Those spaces must then be ignored.
The algorithm proceeds in steps. At each step, the algorithm reads exactly
one symbol from the input stream. (At the last step, the input symbol is
the "end-of-line" symbol.) Also, during each step, the algorithm performs
calculations that possibly pop and push the stack.
After the final step, the algorithm yields a single integer as output.
For the above example, the output is 61.
-
The program should print an appropriate error message if the input line
is unacceptable.
-
The stack contains unfulfilled obligations (as always).
An exact algorithm will be described in a page on the web. (Not yet written.)
-
You must use only one stack. A program that uses two or
more stacks, or an array, or any other unbounded memory structure, is
unacceptable. You may use a small number of other variables.
(Note that in my code I use at most 3.)
Your program may not use recursive functions in any form, regardless of how
cleverly disguised. That is because recursion uses a stack
(provided by the compiler) which violates the rule against having two stacks.
For the same reason, you may not use any recursive data structure, other
than the linked list used to implement the stack. (For example, you
may not have a binary search tree, although I cannot imagine how that would
help.)
You may use "peek" and "putback." But be careful. These inputs are then
stored in a buffer, which is a variable.
-
Write one function "main" and two implementations of
"stack" one of which is an array implementation and the other a linked
list implementation.
Design the files so that "main" does exactly the same thing, regardless
of which of the two stack implentations is used, and without altering
the file that contains "main" in any way.
-
As always, the programs must be executed on our system. You should
use the command: g++ -fhandle-exceptions
-
Turn in all files, including a file that shows several sample runs.
All files must be turned in electronically to the teaching assisant.
His email address is schj. The deadline for electronic submission
is Wednesday, February 16. The submission must be timestamped
before midnight.
Here is how that is done.
Be sure to include the string "CSC 269 001 Hw3" in the subject field
of your email.
-
Hints
