Topic 15 Implementing and Using StacksStack OverflowSharper ToolsStacksStack OperationsSlide 6Common Stack ErrorAttendance Question 1Corrected VersionImplementing a stackApplications of StacksProblems that Use StacksMathematical CalculationsInfix and Postfix ExpressionsAttendance Question 2Evaluation of Postfix ExpressionsInfix to PostfixInfix to Postfix ConversionSimple ExampleSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26ExampleBalanced Symbol CheckingAlgorithm for Balanced Symbol CheckingAlgorithm in practiceCS 307 Fundamentals of Computer Science Stacks1Topic 15Implementing and Using Stacks"stack n.The set of things a person has to do in the future. "I haven't done it yet because every time I pop my stack something new gets pushed." If you are interrupted several times in the middle of a conversation, "My stack overflowed" means "I forget what we were talking about." -The Hacker's Dictionary Friedrich L. BauerGerman computer scientistwho proposed "stack methodof expression evaluation"in 1955.Stack OverflowCS 307 Fundamentals of Computer Science Stacks2CS 307 Fundamentals of Computer Science Stacks3Sharper ToolsListsStacksCS 307 Fundamentals of Computer Science Stacks4StacksAccess is allowed only at one point of the structure, normally termed the top of the stack–access to the most recently added item only Operations are limited:–push (add item to stack)–pop (remove top item from stack)–top (get top item without removing it)–clear–isEmpty–size?Described as a "Last In First Out" (LIFO) data structureCS 307 Fundamentals of Computer Science Stacks5Stack OperationsAssume a simple stack for integers.Stack s = new Stack();s.push(12);s.push(4);s.push( s.top() + 2 );s.pop()s.push( s.top() );//what are contents of stack?CS 307 Fundamentals of Computer Science Stacks6Stack OperationsWrite a method to print out contents of stack in reverse order.CS 307 Fundamentals of Computer Science Stacks7Common Stack ErrorStack s = new Stack();// put stuff in stackfor(int i = 0; i < 5; i++)s.push( i );// print out contents of stack // while emptying it. (??)for(int i = 0; i < s.size(); i++)System.out.print( s.pop() + “ “);// What is output?Attendance Question 1What is output of code on previous slide?A 0 1 2 3 4B 4 3 2 1 0C 4 3 2D 2 3 4E No output due to runtime error.CS 307 Fundamentals of Computer Science Stacks8CS 307 Fundamentals of Computer Science Stacks9Corrected VersionStack s = new Stack();// put stuff in stackfor(int i = 0; i < 5; i++)s.push( i );// print out contents of stack // while emptying itint limit = s.size();for(int i = 0; i < limit; i++)System.out.print( s.pop() + “ “);//or// while( !s.isEmpty() )// System.out.println( s.pop() );CS 307 Fundamentals of Computer Science Stacks10Implementing a stackneed an underlying collection to hold the elements of the stack2 basic choices–array (native or ArrayList)–linked listarray implementationlinked list implementationSome of the uses for a stack are much more interesting than the implementation of a stackCS 307 Fundamentals of Computer Science Stacks11Applications of StacksCS 307 Fundamentals of Computer Science Stacks12Problems that Use StacksThe runtime stack used by a process (running program) to keep track of methods in progressSearch problemsUndo, redo, back, forwardCS 307 Fundamentals of Computer Science Stacks13Mathematical CalculationsWhat is 3 + 2 * 4? 2 * 4 + 3? 3 * 2 + 4?The precedence of operators affects the order of operations. A mathematical expression cannot simply be evaluated left to right. A challenge when evaluating a program.Lexical analysis is the process of interpreting a program. Involves TokenizationWhat about 1 - 2 - 4 ^ 5 * 3 * 6 / 7 ^ 2 ^ 3CS 307 Fundamentals of Computer Science Stacks14Infix and Postfix ExpressionsThe way we are use to writing expressions is known as infix notationPostfix expression does not require any precedence rules3 2 * 1 + is postfix of 3 * 2 + 1evaluate the following postfix expressions and write out a corresponding infix expression:2 3 2 4 * + * 1 2 3 4 ^ * +1 2 - 3 2 ^ 3 * 6 / + 2 5 ^ 1 -Attendance Question 2What does the following postfix expression evaluate to?6 3 2 + *A.18B.36C.24D.11E.30 CS 307 Fundamentals of Computer Science Stacks15CS 307 Fundamentals of Computer Science Stacks16Evaluation of Postfix ExpressionsEasy to do with a stackgiven a proper postfix expression:–get the next token–if it is an operand push it onto the stack–else if it is an operator•pop the stack for the right hand operand•pop the stack for the left hand operand•apply the operator to the two operands•push the result onto the stack–when the expression has been exhausted the result is the top (and only element) of the stackCS 307 Fundamentals of Computer Science Stacks17Infix to PostfixConvert the following equations from infix to postfix:2 ^ 3 ^ 3 + 5 * 111 + 2 - 1 * 3 / 3 + 2 ^ 2 / 3Problems:Negative numbers?parentheses in expressionCS 307 Fundamentals of Computer Science Stacks18Infix to Postfix ConversionRequires operator precedence parsing algorithm–parse v. To determine the syntactic structure of a sentence or other utteranceOperands: add to expressionClose parenthesis: pop stack symbols until an open parenthesis appearsOperators: Have an on stack and off stack precedencePop all stack symbols until a symbol of lower precedence appears. Then push the operatorEnd of input: Pop all remaining stack symbols and add to the expressionCS 307 Fundamentals of Computer Science Stacks19Simple ExampleInfix Expression: 3 + 2 * 4PostFix Expression:Operator Stack: Precedence TableSymbol Off Stack On StackPrecedence Precedence+ 1 1- 1 1* 2 2/ 2 2^ 10 9( 20 0CS 307 Fundamentals of Computer Science Stacks20Simple ExampleInfix Expression: + 2 * 4PostFix Expression: 3Operator Stack: Precedence TableSymbol Off Stack On StackPrecedence Precedence+ 1 1- 1 1* 2 2/ 2 2^ 10 9( 20 0CS 307 Fundamentals of Computer Science Stacks21Simple ExampleInfix Expression: 2 * 4PostFix Expression: 3Operator Stack: + Precedence TableSymbol Off Stack On StackPrecedence Precedence+ 1 1- 1 1* 2 2/ 2 2^ 10 9( 20 0CS 307 Fundamentals of Computer Science Stacks22Simple ExampleInfix Expression: * 4PostFix Expression: 3 2Operator Stack: + Precedence TableSymbol Off Stack On StackPrecedence Precedence+ 1 1- 1 1* 2 2/ 2 2^ 10 9( 20 0CS 307 Fundamentals of Computer Science Stacks23Simple ExampleInfix
View Full Document