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

-
This is a description of a Complete Algorithm for the problem. It is
not the only way to work the problem.
-
The Complete Algorithm is quite similar to the Limited Algorithm.
There is a stack where each item is either an integer or a character.
You will note from my code that I can push a value of either type int
or char onto the stack, but that the stack items themselves are of a
mysterious type which I call "intorchar." Somehow, I am able to
compare those to expressions of type either int or char, and I can
somehow query what type they are, such as in "if (top1 == number)"
There are a large number of ways to implement a stack of this "mixed type"
and my way is just one of many, and not even the best. Figuring out
how to do this is one of the minor challenges of this assignment.
-
The hardest two parts of the assignment are handling multidigit numerals,
and handling the unary "-" operator.
-
The Complete Algorithm consists of steps.
During one step, exactly one character is read from the
input stream. (The end-of-line symbol is the last character read.)
During one step, temporary variables are created, used, and destroyed.
The number of these is bounded, never more than 4 in my code. (In the
Limited Algorithm, there are never more than 3.)
Between steps, all of the algorithm's memory is in the stack. That is,
the temporary variables are not used to carry information from one step
to the next.
-
We say that the stack is valid if it could occur during the
execution of the algorithm with some valid input.
For example, [:5:-:50:*:(6:+:-8:/:65:# is a valid stack.
Try to think of a valid input which would cause that stack at some
point during the calculation. Answer.
For example, [:3:+:4:- is not a valid stack, because, if the algorithm
is properly designed, that stack can never occur.
-
Detailed Description of One Step.
More Helpful Clues.
