UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 10.4 Free with a free account
Stack Applications: Expressions, Undo and Call Tracking
Data Structures and Algorithms · Chapter 10: Stacks, Queues, and DequesSection 10.4 · lesson 42 of 8714 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Queue Applications: Scheduling, Buffering, Traversal →← Adding and Removing at Both Ends of a SequenceNext lesson: Queue Applications: Scheduling, Buffering, Traversal →
In this lesson
Stacks for bracket matching, postfix evaluation, undo, and call tracking.
- Check bracket balance with a stack and identify the three ways it fails
- Evaluate postfix expressions and convert infix to postfix with a stack
- Implement undo and redo with two stacks
- Explain how the call stack tracks methods and how an explicit stack replaces recursion
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (2,091 words). Read along, or search it.
Opening Question
Brackets, Undo, and Return Addresses
Leave one bracket out of place, and a compiler spots it at once. Press undo three times, and an editor takes back exactly the right three things. Both rely on the same small rule: the item added last is the item removed first. That's a stack. A compiler uses one to check brackets and to evaluate arithmetic. An editor uses two, for undo and redo. And a running program uses one to remember where to return. So what makes one rule fit so many problems? And how do you tell when a stack is the right tool?
Key Idea
Newest Unfinished Item Finishes First
Here's the pattern. A stack is the right tool whenever the most recent unfinished thing must be finished first. An opening bracket is unfinished until its closer arrives. A number is unfinished until the operator that uses it arrives. An action stays undoable until it's taken back. And a method call is unfinished until the method returns. New items pile on top of old ones, and the item on top is dealt with next. The bracket and expression algorithms each make one pass over their input. Each item is pushed once and popped at most once, so each runs in time proportional to the input.
Definition
What Balanced Brackets Mean
Start with brackets. Balanced means two things: every opener has a closer of the same kind, and the pairs nest like boxes inside boxes. So a, square bracket i, equals, parenthesis b plus c, times d, is balanced. But parenthesis, square bracket, close parenthesis, close square bracket, is not. It has two openers and two closers. But the round one closes while the square one inside it is still open. Counting can't catch that. Order matters, and order is what a stack remembers.
Implementation
Checking Brackets with a Stack
The method reads the text left to right, and ignores everything that isn't a bracket. On an opener, it pushes the opener's position. On a closer, the stack must not be empty, and the opener popped from the top must be the matching kind. Otherwise the text fails. At the end, the stack must be empty. Any opener still on it was never closed. Storing positions instead of symbols lets each failure say exactly where the trouble is. Run it on six strings. For curly, square, round, and back out, the stack grows to three openers, and each closer removes exactly the one on top. That's balanced, and so is the assignment.
Worked Example
Three Ways Brackets Fail
The other four results show the three ways to fail. In parenthesis, square, close parenthesis, close square, the top is a square bracket when the round closer arrives: the wrong kind. In open, close, close, the last closer finds the stack empty. That's a closer with no opener. In open, open, close, one opener is still on the stack at the end: it was never closed. And closing curly, then opening curly, fails on its very first symbol.
Definition
Infix Versus Postfix Notation
Next, arithmetic. People write infix, with each operator between its operands: three plus four times two. To read it, you need to know that times ranks above plus. Postfix, also called reverse Polish notation, puts each operator after its operands. The operators appear in the order they act, so no ranks and no parentheses are needed. A stack evaluates postfix in one pass. A number is pushed. An operator pops its two operands, applies itself, and pushes the result. At the end, exactly one value must remain.
Implementation
A Postfix Evaluator and Pop Order
Here's the evaluator. An operator first checks that two operands are waiting, then pops them, applies itself, and pushes the result. The order of the two pops matters. The first value popped is the right operand, and the second is the left. For plus and times it makes no difference. For minus and divide, it does. Eight, two, minus must give six, so eight, popped second, is the left operand. Swap them, and you'd get minus six. Run six tests. Five, one, two, plus, four, times, plus, three, minus, gives fourteen. And nine, three, one, minus, divide, two, times gives eight, not nine, because dividing two ints drops the fraction. The last two aren't valid postfix. In one plus, the operator finds only one operand, and in one two, two values are left. Both come back as null instead of crashing.
Trace
Evaluating a Postfix Expression to Fourteen
Follow the stack for five, one, two, plus, four, times, plus, three, minus. In infix, that's five plus four times the sum of one and two, minus three. Five, one and two are pushed. Plus pops two and one, and pushes three. Four is pushed, and times pops four and three, and pushes twelve. Plus pops twelve and five, and pushes seventeen. Three is pushed, and minus pops three and seventeen, and pushes fourteen: the single value left.
Quick Check
The Right Operand Pops First
Quick check. This main evaluates nine, five, two, minus, times. Watch the order of the pops. What does it print? Pause and predict. It prints twenty-seven. When minus arrives, two is on top, so two is the right operand and five the left: five minus two is three. Then times pops three and nine, and nine times three is twenty-seven. Minus twenty-seven comes from popping the operands in the wrong order, two minus five. And forty-three applies times before minus, which postfix never does.
Algorithm
Converting Infix to Postfix
Postfix is easy to evaluate. Getting there from infix is a second stack algorithm. This time, the stack holds operators that can't be written yet, because something later might have to go first. An operand goes straight to the output. An operator first pops every waiting operator of equal or higher rank to the output, then pushes itself. An opening parenthesis is pushed. A closing one pops operators until it reaches the opener, which is discarded. At the end, everything left is popped. Times and divide rank two. Plus and minus rank one. Equal ranks act left to right.
Implementation
Ranks and Parentheses in Code
Here it is as code. The while loop pops waiting operators while the top's rank is equal or higher, and the closing parenthesis loop pops back to the opener, then discards it. This main converts four expressions and evaluates each result. In three plus four times two, times is stronger than plus, so it's written first, though it comes later. With parentheses around three plus four, plus is written first instead. And eight minus three minus two keeps its left to right order: three.
Trace
Converting an Expression with Parentheses
Trace two times, open, three plus four, close, minus five. Two goes out. Times is pushed, and so is the opener. Three goes out. Plus is pushed on top of the opener, and four goes out. The closer pops plus to the output, and discards the opener. Now watch minus arrive. The stack holds times, which ranks higher, so times is popped first. That's why two, three, four, plus, times is complete before five is written. Five goes out, and at the end, minus is popped. Evaluated, that's nine.
Common Mistake
Equal or Higher, Not Strictly Higher
Why equal or higher, and not just higher? Popping equal ranks too makes operators of the same rank act left to right. Change the comparison to a strict greater than, and run it again. Only one line changes: eight minus three minus two becomes eight, three, two, minus, minus, which is seven. The strict version leaves the first minus waiting, so it computes eight minus the quantity three minus two. One character changed the answer. And if the input might hold a stray closing parenthesis, run the bracket check first. Otherwise the conversion would pop from an empty stack.
Application
Undo and Redo with Two Stacks
Now undo and redo. The most recent action must be undone first, which is the stack rule again. Redo needs a second stack. An undone action doesn't vanish: it moves to the redo stack, in case you change your mind. Doing a new action performs it, pushes it on the undo stack, and clears the redo stack. Undo pops from undo, reverses it, and pushes it onto redo. Redo does the opposite.
Worked Example
A Text Editor's History
Here, each action is a piece of typed text. Type, undo and redo follow those three rules exactly, and the stacks print top first. Type hello, space world, and an exclamation mark. Undo twice: the text is back to hello, and the two pieces wait on redo, with space world on top. Redo brings back space world. Then type a question mark: a new action, so the redo stack is cleared. The final redo has nothing to do. The exclamation mark is gone for good, and that's deliberate: it belonged to a version of the text that no longer exists. Real editors store a small description of each action that knows how to reverse itself, and many cap the history. The two-stack structure is the same.
Quick Check
A New Action Clears Redo
Quick check. With the same editor, type hi, then type space there. Undo, redo, and undo again. Then type an exclamation mark, and press redo. What text is left? Pause and predict. It leaves hi, exclamation mark. The second undo put space there back on the redo stack. Typing the exclamation mark was a new action, so it cleared the redo stack, and the last redo found nothing. Hi, exclamation, space there, is what you'd get if typing didn't clear redo. And hi there, exclamation, would mean the second undo never happened.
Application
Tracking Method Calls
The last application runs inside every program. The call stack holds one frame for each method that has started and not yet returned, and the method called last returns first. To see it from outside, this tracker keeps its own stack. Each method records enter when it starts, and exit when it's about to return. Main calls report, and report calls average. While average runs, the two calls beneath it wait. When average exits, report resumes, and calls format, which takes average's place. Average equals seven prints while only main and report remain. And the chain of method names printed when a program fails is a copy of this stack, at that moment.
Technique
Replacing Recursion with an Explicit Stack
Since a recursive call is just a frame on the call stack, a recursive method can be rewritten with a stack you manage yourself. Fibonacci makes two recursive calls. In the stack version, each waiting number k, of two or more, is replaced by two smaller problems: k minus one, and k minus two. A number below two simply adds itself to the total. Both versions agree: five, fifty-five, and six thousand, seven hundred sixty-five. The deepest the stack grew was three, six and eleven. That stack lives in ordinary memory, not the limited call stack, and the program can inspect it. The price is readability. The same idea drives depth-first graph traversal, in chapter seventeen.
Decision Guide
When a Stack Fits
So how do you know a stack fits? Listen for reverse order in the problem: the most recent, go back, the innermost, undo, finish what was started last. Serve in order of arrival points to a queue instead. Work at both ends points to a deque. And looking at an item in the middle, by position, needs an array or a list. Three questions help. Does the problem always deal with the newest pending item first? Do I ever need to see below the top? And what is pushed, and what event pops it?
Common Mistake
A Queue Fails on Nested Brackets
The wrong structure doesn't always fail loudly. This checker uses a queue, so a closer is compared with the oldest opener, not the newest. On parenthesis pair, square pair, it agrees with the stack, because nothing is nested. But every nested string is rejected, though all are balanced. A test suite with only flat examples would never reveal it. So test the nested cases too.
Common Mistakes
Stack Application Pitfalls
A few more mistakes to avoid. Test is empty before every pop, so a stray closer or a lone operator can't crash the program. Check the stack at the end: empty for brackets, exactly one value for postfix. Discard the opening parenthesis after popping back to it. And in a call tracker, pair every enter with an exit, including early returns.
Key Takeaways
Stack Application Essentials
To sum up. A stack fits whenever the newest unfinished thing must finish first. Brackets push openers, and fail on the wrong kind, a missing opener, or an opener left at the end. Postfix pops two operands per operator, right operand first. Infix converts with a stack of waiting operators, popping equal or higher rank. Undo and redo use two stacks, and a new action clears redo. And the call stack is a stack of unfinished methods.
Think About It
Back and Forward Buttons
Something to think about. A browser's back button returns to the page you visited just before this one. Which structure fits it? And how would a forward button work, and what should visiting a new page do to it?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Stack Applications: Expressions, Undo and Call Tracking
How do you check for balanced parentheses using a stack?
How do you evaluate a postfix expression with a stack?
How do you convert infix to postfix using a stack?
How do undo and redo work with two stacks?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →