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 15Il ti dUiStkImplementing and Using Stacks"stack n.Th t f thi h t d i th f t "I h 'tThe 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 gp y pmiddle of a conversation, "My stack overflowed" means "I forget what we were talking about." -The Hacker's Dictionary Friedrich L BauerFriedrich L. BauerGerman computer scientistwho proposed "stack methodof expression evaluation"CS 307 Fundamentals of Computer Science Stacks1of expression evaluationin 1955.Stack OverflowCS 307 Fundamentals of Computer Science Stacks2Sharper ToolsListsStacksListsCS 307 Fundamentals of Computer Science Stacks3Stacks8Access is allowed only at one point of the structure8Access is allowed only at one point of the structure, normally termed the top of the stack–access to the most recently added item only–access to the most recently added item only8 Operations are limited:–push (add item to stack)push (add item to stack)– pop (remove top item from stack)–top (get top item without removing it)p(g p g )– clear–isEmpty–size?8Described as a "Last In First Out" (LIFO) d t t tCS 307 Fundamentals of Computer Science Stacks4(LIFO) data structureStack OperationsAssume a simple stack for integers.Stack s = new Stack();s.push(12);s push(4);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 Stacks5Stack OperationsWrite a method to print out contents of stack in reverse order.CS 307 Fundamentals of Computer Science Stacks6Common Stack ErrorStack s = new Stack();// put stuff in stackfor(int i 0; i < 5; i++)for(int i = 0; i < 5; i++)s.push( i );// print out contents of stack// print out contents of stack // while emptying it. (??)for(int i = 0; i < s.size(); i++)System.out.print( s.pop() + “ “);// Wh t i t t?// What is output?CS 307 Fundamentals of Computer Science Stacks7Attendance Question 188What is output of code on previous slide?A 0 1 2 3 4B 4 3 2 1 0C432C 4 3 2D 2 3 4EN d iE No output due to runtime error.CS 307 Fundamentals of Computer Science Stacks8Corrected VersionStack s = new Stack();// put stuff in stackfor(int i = 0; i < 5; i++)for(int i = 0; i < 5; i++)s.push( i );// print out contents of stack p// while emptying itint limit = s.size();for(int i = 0; i < limit; i++)System.out.print( s.pop() + “ “);////or// while( !s.isEmpty() )CS 307 Fundamentals of Computer Science Stacks9// System.out.println( s.pop() );Implementing a stack8d d l i ll i h ld h l8need an underlying collection to hold the elements of the stack82b i h i82 basic choices– array (native or ArrayList)linked list–linked list8array implementation8linked list implementation8Some of the uses for a stack are much more interesting than the implementation of a stackCS 307 Fundamentals of Computer Science Stacks10interesting than the implementation of a stackApplications of StacksApplications of StacksCS 307 Fundamentals of Computer Science Stacks11Problems that Use Stacks88The runtime stack used by a process (running program) to keep track of methods in progress8Search problems8Undo, redo, back, forwardU do, edo, bac , o a dCS 307 Fundamentals of Computer Science Stacks12Mathematical CalculationsWhti32*4?2*43?3*24?What is 3 + 2 * 4? 2 * 4 + 3? 3 * 2 + 4?The precedence of operators affects the df ti Ath tilorder of operations. A mathematical expression cannot simply be evaluated left to rightright. A challenge when evaluating a program.Lil liith fLexical analysis is the process of interpreting a program. Il TkitiInvolves TokenizationWh t b t 124^5*3*6/7^2^3CS 307 Fundamentals of Computer Science Stacks13What about 1 -2 -4 ^ 5 * 3 * 6 / 7 ^ 2 ^ 3Infix and Postfix Expressions8Th t iti8The way we are use to writing expressions is known as infix notationnotation8Postfix expression does not 8idl8require any precedence rules83 2 * 1 + is postfix of 3 * 2 + 18evaluate the following postfix expressions and write out a di i fi icorresponding infix expression:2 3 2 4 * + * 1 2 3 4 ^ * +1232^3*6/+25^1CS 307 Fundamentals of Computer Science Stacks141 2 -3 2 ^ 3 * 6 / +2 5 ^ 1 -Attendance Question 288What does the following postfix expression evaluate to?6 3 2 + *A.188B. 36C24C.24D. 11E. 30 CS 307 Fundamentals of Computer Science Stacks15Evaluation of Postfix Expressions8Etdithtk8Easy to do with a stack8given 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 operandshth lt t th t k• 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 Stacks16result is the top (and only element) of the stackInfix to Postfix88Convert 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 Stacks17Infix to Postfix Conversion8R i t d i l ith8Requires 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 operatorprecedence appears. Then push the operatorEnd of input: Pop all remaining stack symbols and add to the expressionCS 307 Fundamentals of Computer Science Stacks18add to the expressionSimple ExampleInfix Expression:3+2*4Infix Expression: 3 + 2 4PostFix Expression:Operator Stack:Operator Stack:Precedence TableSymbol Off Stack On StackPrecedence Precedence+11+11-11*22/22/22^109(200CS 307 Fundamentals of Computer Science Stacks19Simple ExampleInfix Expression:+2*4Infix Expression: + 2 4PostFix Expression: 3Operator Stack:Operator Stack:Precedence TableSymbol Off Stack On StackPrecedence Precedence+11+11-11*22/22/22^109(200CS 307 Fundamentals of Computer Science Stacks20Simple ExampleInfix Expression:2*4Infix Expression: 2 4PostFix Expression: 3Operator Stack:+Operator Stack:+Precedence TableSymbol Off Stack On StackPrecedence Precedence+11+11-11*22/22/22^109(200CS 307 Fundamentals of Computer Science Stacks21Simple


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?