Stacks in Action
Although a stack is not typically used to store data on a long-term basis, it can be a great tool to handle temporary data as part of various algorithms. Here’s an example:
Let’s create the beginnings of a JavaScript linter—that is, a program that inspects a programmer’s JavaScript code and ensures that each line is syntactically correct. It can be very complicated to create a linter, as there are many different aspects of syntax to inspect. We’ll focus on just one specific aspect of the linter—opening and closing braces. This includes parentheses, square brackets, and curly braces—all common causes of frustrating syntax errors.
To solve this problem, let’s first analyze what type of syntax is incorrect when it comes to braces. If we break it down, we’ll find that there are three situations of erroneous syntax:
The first is when there is an opening brace that doesn’t have a corresponding closing brace, such as this:
| | (var x = 2; |
We’ll call this Syntax Error Type #1.
The second is when there is a closing brace that was never preceded by a corresponding opening brace:
| | var x = 2;) |
We’ll call that Syntax Error Type #2.
The third, which we’ll refer to as Syntax Error Type #3, is when a closing brace is not the same type of brace as the immediately preceding opening brace, such as:
| | (var x = [1, 2, 3)]; |
In the preceding example, there is a matching set of parentheses, and a matching pair of square brackets, but the closing parenthesis is in the wrong place, as it doesn’t match the immediately preceding opening brace, which is a square bracket.
How can we implement an algorithm that inspects a line of code and ensures that there are no syntax errors in this regard? This is where a stack allows us to implement a beautiful linting algorithm, which works as follows:
We prepare an empty stack, and then we read each character from left to right, following these rules:
-
If we find any character that isn’t a type of brace (parenthesis, square bracket, or curly brace), we ignore it and move on.
-
If we find an opening brace, we push it onto the stack. Having it on the stack means we’re waiting to close that particular brace.
-
If we find a closing brace, we inspect the top element in the stack. We then analyze:
-
If there are no elements in the stack, that means we’ve found a closing brace without a corresponding opening brace beforehand. This is Syntax Error Type #2.
-
If there is data in the stack, but the closing brace is not a corresponding match for the top element of the stack, that means we’ve encountered Syntax Error Type #3.
-
If the closing character is a corresponding match for the element at the top of the stack, that means we’ve successfully closed that opening brace. We pop the top element from the stack, since we no longer need to keep track of it.
-
-
If we make it to the end of the line and there’s still something left on the stack, that means there’s an opening brace without a corresponding closing brace, which is Syntax Error Type #1.
Let’s see this in action using the following example:
After we prepare an empty stack, we begin reading each character from left to right:
Step #1: We begin with the first character, which happens to be an opening parenthesis:
Step #2: Since it’s a type of opening brace, we push it onto the stack:
We then ignore all the characters var x = , since they aren’t brace characters.
Step #3: We encounter our next opening brace:
Step #4: We push it onto the stack:
We then ignore the y:
Step #5: We encounter the opening square bracket:
Step #6: We add that to the stack as well:
We then ignore the 1, 2, 3.
Step #7: We encounter our first closing brace—a closing square bracket:
Step #8: We inspect the element at the top of the stack, which happens to be an opening square bracket. Since our closing square bracket is a corresponding match to this final element of the stack, we pop the opening square bracket from the stack:
Step #9: We move on, encountering a closing curly brace:
Step #10: We read the last element in the stack. It’s an opening curly brace, so we’ve found a match. We pop the opening curly brace from our stack:
Step #11: We encounter a closing parenthesis:
Step #12: We read the last element in the stack. It’s a corresponding match, so we pop it from the stack, leaving us with an empty stack.
Since we’ve made it through the entire line of code, and our stack is empty, our linter can conclude that there are no syntactical errors on this line (that relate to opening and closing braces).
Here’s a Ruby implementation of the preceding algorithm. Note that Ruby has push and pop methods built into arrays, and they are essentially shortcuts for adding an element to the end of the array and removing an element from the end of an array, respectively. By only using those two methods to add and remove data from the array, we effectively use the array as a stack.
| | class Linter |
| | |
| | attr_reader :error |
| | |
| | def initialize |
| | # We use a simple array to serve as our stack: |
| | @stack = [] |
| | end |
| | |
| | def lint(text) |
| | # We start a loop which reads each character in our text: |
| | text.each_char.with_index do |char, index| |
| | |
| | if opening_brace?(char) |
| | |
| | # If the character is an opening brace, we push it onto the stack: |
| | @stack.push(char) |
| | elsif closing_brace?(char) |
| | |
| | if closes_most_recent_opening_brace?(char) |
| | |
| | # If the character closes the most recent opening brace, |
| | # we pop the opening brace from our stack: |
| | @stack.pop |
| | |
| | else # if the character does NOT close the most recent opening brace |
| | |
| | @error = "Incorrect closing brace: #{char} at index #{index}" |
| | return |
| | end |
| | end |
| | end |
| | |
| | if @stack.any? |
| | |
| | # If we get to the end of line, and the stack isn't empty, that means |
| | # we have an opening brace without a corresponding closing brace: |
| | @error = "#{@stack.last} does not have a closing brace" |
| | end |
| | end |
| | |
| | private |
| | |
| | def opening_brace?(char) |
| | ["(", "[", "{"].include?(char) |
| | end |
| | |
| | def closing_brace?(char) |
| | [")", "]", "}"].include?(char) |
| | end |
| | |
| | def opening_brace_of(char) |
| | {")" => "(", "]" => "[", "}" => "{"}[char] |
| | end |
| | |
| | def most_recent_opening_brace |
| | @stack.last |
| | end |
| | |
| | def closes_most_recent_opening_brace?(char) |
| | opening_brace_of(char) == most_recent_opening_brace |
| | end |
| | end |
If we use this class as follows:
| | linter = Linter.new |
| | linter.lint("( var x = { y: [1, 2, 3] } )") |
| | puts linter.error |
We will not receive any errors since this line of JavaScript is correct. However, if we accidentally swap the last two characters:
| | linter = Linter.new |
| | linter.lint("( var x = { y: [1, 2, 3] ) }") |
| | puts linter.error |
We will then get the message:
| | Incorrect closing brace: ) at index 25 |
If we leave off the last closing parenthesis altogether:
| | linter = Linter.new |
| | linter.lint("( var x = { y: [1, 2, 3] }") |
| | puts linter.error |
We’ll get this error message:
| | ( does not have a closing brace |
In this example, we use a stack to elegantly keep track of opening braces that have not yet been closed. In the next chapter, we’ll use a stack to similarly keep track of functions of code that need to be invoked, which is the key to a critical concept known as recursion.
Stacks are ideal for processing any data that should be handled in reverse order to how it was received (LIFO). The “undo” function in a word processor, or function calls in a networked application, are examples of when you’d want to use a stack.