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

-
I have written a Limited Algorithm that can only
handle some expressions. In an expression which is an input for
the Limited Algorithm, the only operators allowed are "+" and "-",
and the only numerals allowed are those that are written with a
single digit, that is, 0 through 9. (Any integer, however, may
occur in the computation. For example: "5+7" would be a valid
input for the Limited Algorithm, but "11+1" would not be a valid input.)
-
Example.
Here is the Sequence of Configurations
of the Limited Algorithm, given the input string "-(4-(3+4)-(-1+4)-9)".
Every time there is a push or a pop, the configuration changes.
A configuration consist of three parts, the stack, the temporary
variables, and the input stream.
The stack is represented by zero or more items separated by colons.
Note that if the stack is empty, there is just one colon.
An item in the stack is either an integer or a character.
There are zero to three temporary variables, separated by colons,
and surrounded by angle brackets. Each is either an integer or
a character.
The input stream consists of all unread characters. The last character
is the end-of-line character, which finally disappears when it is read.
-
Code for the Limited Algorithm.
I have removed the portion of the code that prints out the sequence
of configurations, so the code you see only does the computation and
prints the value.
The code is obviously incomplete, because it contains an included file.
Try to imagine what I wrote in there.
I have inserted deliberate hard-to-find errors. The code is unusable
until the errors are detected and fixed. This is to discourage simply
copying my code.
-
Discussion of the Limited Algorithm.
Each item on the stack represents (as always) an unfulfilled obligation.
An item is popped off the stack to examine
it to decide what to do or to fulfill the obligation it represents.
The algorithm sometimes pops an item, examines it, and then decides
whether its obligation can be fulfilled at this time or not.
If not, the item must be pushed back onto the stack.
Here are the obligations the items represent:
-
A number must be used either in a computation or as the final value.
-
The bottom symbol "[" must be paired with the end of line symbol.
-
A left parenthesis must be paired with a right parenthesis.
-
An operator must be combined with one or two numbers (operands) and
the appropriate computation done.
An item is pushed onto the stack if the obligation it represents is
unfulfillable at that time. For example, an operator symbol is pushed
onto the stack and remains there until its right operand is known.
In the Limited Algorithm, an operator is only popped when the algorithm
knows that the right operand is available. But in the Final Algorithm
(which you must write for the assignment) it is sometimes necessary
to pop an operator not knowing whether its right operand is available,
then push it back onto the stack if necessary. (See below for a
discussion.)
-
Modifications Needed for Operator Precedence
If operators all have the same precedence, we can always know the
right operand of an operator when it is popped off the stack.
But generally, this is not the case.
Consider a situation in which the multiplication and division operators
have the same precedence with a left-first rule, but higher precedence
than the addition operator. (This is the normal situation in most
programming languages.)
Suppose that the current stack is :[:4:*:3: and the input symbol is "/".
The algorithm must push the division sign, as its right operand is
unkown, but before that, it must "clear" the stack by meeting any
fulfillable obligations on the stack. The obligation to multiply
can now be fulfilled, but the algorithm does not know that until
it pops the 3 and then the multiplication symbol. Seeing that symbol,
the algorithm pops the left operand, multiplies, and then pushes
the product. The stack is now :[:12: after which the algorithm
pushes the division sign, making the stack :[:12:/:
Suppose on the other hand that the stack is :[:4:+:3 and the
input symbol is "/". The algorithm cannot distinguish this situation
from the previous situation until it pops the operator. Seeing
that it is an addition symbol, the algorithm knows that it does not
know the right operand of that operator, and so it cannot yet fulfill
the obligation to add. It pushes everything back onto the stack,
which becomes :[:4+3:/:
-
How to Handle Multidigit Numerals in Input.
Do not make use of any built-in or library facility to read a multidigit
integer. You must read the input stream one character at a time, and
use the stack to hold the unfulfilled obligation to finish reading
the numeral. Here is how that is done:
Use an operator, which we can call "join." Let's write "#" for "join"
Then, if x and y are integers, define x#y to be 10*x+y. Thus, for
example, 27 = 2#7. This works for more than two digits, too;
for example, 645 = 64#5 = 6#4#5.
The concept is for the program to assume that there is a virtual "join"
operator between the digits of any multidigit numeral in the
input stream. An input string can then be considered to be an expression
where every operand is between 0 and 9. For example, the string
3+306*67 will be read as 3+3#0#6*6#7. The operator "#" is
left-associative and has higher precedence than multiplication and division.
One problem is that the algorithm does not know that a digit is the
last digit in a numeral until it reads the next input character.
One way to handle that problem is to allow "#" to double as a postfix
operator which does nothing, that is, n# = n for any integer n. Then,
for example, 64 could be written 6#4#.
The string 3+306*67 would then be read as 3#+3#0#6#*6#7#. The advantage
of this approach is that a "#" can be pushed onto the stack without
knowing whether the next input character is a digit.
-
Suggested Plan.
Write your algorithm in stages. At first, write the Limited Algorithm.
Then, expand to handle operators of different precedence. Then,
expand to allow numerals of one or more digits in input.
Write just one of the two implementations of the ADT "stack" at first.
After you get everything running, write the other implementation,
with exactly the same user interface.
More Hints.
