CMIS 240  DE

Week 5


This week we'll do half of chapter 4: the sections on stacks and
templates.  

A computer stack is like a real-life stack of plates or trays at the
cafeteria except that it's impossible to "cheat" and reach in and
access anything except the item at the top of the stack. A stack is a
list that can be accessed only at one end (called the "top").  It's
restricted in how its items can be accessed.  Adding an item to the
stack is called "pushing" (pushing that tray onto the top of the
stack), removing an item is called "popping" (pops off the
spring-loaded stack).  With a stack abstract data type the client can
not access the items in any other way.  The item that is popped is the
one that was most recently pushed; this is the "last in, first out"
(LIFO) characteristic of a stack, sometimes known as a LIFO list.
There's no "search" function of a stack (they are not intended for
such a use).  Length is usually irrelevant in most stack applications,
so there's no "length" function.  Nor is there an iterator.  There is
a function to check to see if the stack is empty; this function is
important for preventing stack "underflow" (attempt to pop an empty
stack) and to check if some phase of processing has completed.

Stacks are simpler kinds of lists than the Sorted and Unsorted lists
of chapter 3.  So why use something that's simpler?  There are lots of
situations that call for a stack-like access of the data.  Many of
those situations are when you need to process data in the reverse
order of its creation (or input).  The long drawn out example in the
book is such a situation (converting a string of digits into the
fractional part of a real number, which is what cin does when it
inputs a real number).  The code on page 185 has a loop pushing digits
onto a stack of characters (each item is a character), then a loop
popping them off the stack, processing each, thus allowing processing
in the reverse order of the data's generation.  If you're thinking
that an array could be used for the same purpose, you're correct; the
array would be being used as a stack.  But it's better (safer and more
efficient, programmer timewise) to use an abstract data type
specifically tailored for such data access.  


Note that there's a slight problem with the driver on page 185 and
the StackType class of page 187: the class uses an array of ItemType
to implement the stack and the parameter to the Push member function
must be an ItemType but the client is trying to pass a char (the
numeral variable) to Push.  ItemType needs to be a char and the client
needs to have an Itemtype variable which is Initialized with the
numeral.

  ItemType item;
...
  inFile.get(numeral);
  if (isdigit(numeral) {
    item.Initialize(numeral);
    stack.Push(item);

Something similar or worse needs to be done with the popped item.
Templates will eliminate the need for the ItemType class.

BUT, looking at the online code in the STACK directory we see four
versions of the StackType class.  Versions 2, 3, and 4 use templates
and so ItemType is eliminated.  Version 1 still uses ItemType but it's
no longer a class, merely a typedef int Itemtype; (in the ItemType.h
file).  Sooo, the above complaint doesn't apply to the online code and
the example on page 186 will work by just changing the typedef to
char:
typedef char ItemType;  //in Itemtype.h


I've made a simpler example using a stack of ints.  It's the 
StackType.h
StackType.cpp
stackdr.cpp 
in the StackType1 subdirectory of Chapter4/ directory in the class web
site.  Study the member functions, notice that they are all simple.
This example driver has a loop inputting ints from the user and
pushing them onto a stack of ints, then a loop popping the ints from
the stack until the stack is empty.  But don't be left with the
impression that stacks are only used in this "loop pushing, then loop
popping until empty" style; they can also be used with a more random
mix of pushes and pops.  The case study on postfix evaluation
illustrates a stack that grows and shrinks unpredictably.


Templates are very powerful and useful.  They'll be used for the rest
of the course.  It's important that you study the section that
introduces them.  I've made a version of the stackdr using templates
in the StackType2 subdirectory.  It creates three stack objects all
from the same templated StackType class: a stack of ints, a stack of
char, and a stack of an arbritary struct called thingee.  A Makefile
(or project) is not needed, just compile stackdr.cpp (it includes
StackType.h, which in turn includes StackType.cpp; templates force
this).
I've had reports from some students that VC++ requires that the .cpp be
in the .h file.  Also a report that the latest "service pack" fixes this.
------------------------------------------------------------------

Homework
Due: 6 Oct.


Modify the postfix.cpp program that's in the Postfix subdirectory of
Chapter4 on the class web site so that it handles negative integers
and all the relational operators (==, !=, <, <=, >, >=).  Let boolean
expressions evaluate to 0 or 1 instead of bool values false and true
(I don't think you'll have to have any coercions or casts, bool values
are automatically converted to 0 or 1). Your program can assume that
the user's input is a syntactically correct postfix expression.  The
code to determine if there's a negative number is probably going to be
ugly (i.e. messy and complicated) but some problems just don't have
elegant solutions.

The postfix.cpp is a somewhat simplified implementation of the Case
Study of pages 209-219.  It uses the templated StackType class that's
in StackType2/.  Use the StackType.h and StackType.cpp exactly as is;
do not submit them; submit your postfix.cpp only.

Compilers typically convert infix expressions to postfix form because
it's easier to evaluate postfix expressions at runtime.

Parentheses are not needed to indicate oreder of operations in a
postfix expression.  Postfix expressions are unambiguous.