DOC PREVIEW
UT CS 307 - Topic 15 Implementing and Using Stacks

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Stacks4StacksAccess 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 1What 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 stackneed an underlying collection to hold the elements of the stack2 basic choices–array (native or ArrayList)–linked listarray implementationlinked list implementationSome 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 StacksThe runtime stack used by a process (running program) to keep track of methods in progressSearch problemsUndo, 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 ExpressionsThe way we are use to writing expressions is known as infix notationPostfix expression does not require any precedence rules3 2 * 1 + is postfix of 3 * 2 + 1evaluate 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 2What 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 ExpressionsEasy to do with a stackgiven 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 PostfixConvert 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 ConversionRequires 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

UT CS 307 - Topic 15 Implementing and Using Stacks

Documents in this Course
Midterm 2

Midterm 2

15 pages

Midterm 1

Midterm 1

15 pages

Syllabus

Syllabus

24 pages

s

s

8 pages

Midterm 1

Midterm 1

14 pages

Midterm 2

Midterm 2

14 pages

Recursion

Recursion

14 pages

Midterm 1

Midterm 1

16 pages

Load more
Download Topic 15 Implementing and Using Stacks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Topic 15 Implementing and Using Stacks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Topic 15 Implementing and Using Stacks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?