BACK

Stacks

NEXT

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
ArrayStack.java   [txt]  [exe]   Program 4.7 (intStack):  Array implementation of a pushdown stack
LinkedStack.java  [txt]  [exe]   Program 4.8 (intStack):  Linked-list implementation of a pushdown stack
ObjectStack.java  [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]
Stack.java                Declaration of the Interface Stack  (.txt version)
ArrayStack.java       Array-oriented implementation  (.txt version)
LinkedStack.java     Linked List implementation  (.txt version)

Alternative Implementations from Earlier Text (Koffman & Wolfgang)
StackInt.java           Stack Interface  (.txt version)
ListStack.java         Implementation derived from the Java API List class  (.txt version)
TestStack.java        Very small exerciser program using a ListStack  (.txt version)
LinkedStack.java    Implementation based explicitly on an underlying linked list  (.txt version)
ArrayStack.java      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
RPNcalc.java          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.)
RPNcalcArray.java Same thing, but based on the ArrayStack above    [.txt version]
RPNdrill.java           Same logic, but constructed as a drill program.  [.txt version]
RPNdrill.exe            JSmooth .exe wrapper with the program

PostfixEvaluator.java   Koffman & Wolfgang's implementation of the same thing, with tiny main and debugging code included
SedgePostfix.java        Sedgewick's implementation of a + * calculator.   [txt version]   [exe]
SedgePostPlus.java     Above code expanded to operators -, /, and %.   [txt version]   [exe]

Another Sample Application
TowersOfHanoiShowingStates.java    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.

InfixToPostfix.java   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.
InfixToPostfixParens.java     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