Discussion of an "Abstract Data Type" (ADT)

PowerPoint presentations:    Sahni:  Concepts and Applications      Sahni:  Implementation     Koffman&Wolfgang, Ch. 5
Locally maintained slide sets:      Stacks      Infix

Sedgewick's Stack Examples, with small amplifications by Timothy Rolfe   [txt]  [exe]   Program 4.7 (intStack):  Array implementation of a pushdown stack  [txt]  [exe]   Program 4.8 (intStack):  Linked-list implementation of a pushdown stack  [txt]  [exe]   Program 4.9 (Stack):  Generic pushdown stack [array based]

Alternative Implementations from Earlier Text (Sahni)
SahniStack.jar         All the files required for Sahni's Stack implementations [including utility code not shown below]                Declaration of the Interface Stack  (.txt version)       Array-oriented implementation  (.txt version)     Linked List implementation  (.txt version)

Alternative Implementations from Earlier Text (Koffman & Wolfgang)           Stack Interface  (.txt version)         Implementation derived from the Java API List class  (.txt version)        Very small exerciser program using a ListStack  (.txt version)    Implementation based explicitly on an underlying linked list  (.txt version)      Implementation based explicitly on an underlying array of objects  (.txt version)

Sample Application
Sahni's Lecture 19   Starting at slide 26 for evaluating postfix expressions          Case study:  Reverse Polish Notation calculator, based on a nested minimalist Stack.  [.txt version]
RPNcalc.rtf             Class hand-out:  above code as one page of two-column text.  (Has K & W's PostfixEvaluator as well.) Same thing, but based on the ArrayStack above    [.txt version]           Same logic, but constructed as a drill program.  [.txt version]
RPNdrill.exe            JSmooth .exe wrapper with the program   Koffman & Wolfgang's implementation of the same thing, with tiny main and debugging code included        Sedgewick's implementation of a + * calculator.   [txt version]   [exe]     Above code expanded to operators -, /, and %.   [txt version]   [exe]

Another Sample Application    Towers of Hanoi, using stacks to represent the pins   [txt]
Towers.exe                                         Executable jar within a JSmooth wrapper

Infix Expression Parsing

Link to Wikipedia    The Wikipedia discussion of the infix to postfix conversion using a stack ("Shunting yard algorithm")

WikiExtract.html       Extract from the above giving just the algorithm and a worked example.   [.doc copy]

Link into Clark/Capaul PPT slides for conversion

InToPostExample.jpg  Worked example from an earlier textbook.   Koffman & Wolfgang's implementation of an Infix to Postfix converter [see slides 27 and 28].    [.txt version]
InfixToPostfixParens.html     Pseudocode for the expansion of the above to include parentheses.     Java code.    [.txt version]

Drill Random Number Generator    For use during parsing exercise in class
DemoXlate.exe       Program to demonstrate parsing of parenthesized infix expression
The following is the expression from the syllabus for grades.  Capture this on your clipboard and then run DemoXlate.exe
4.2 - ( 100 - ( Exam1 * 0.15 + Exam2 * 0.15 + Final * 0.30 + Pgms * 0.4 ) ) / 12

Programming Assignment 4 Assignment exercising this material