Stacks in Action
Although a stack isn’t 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. Let’s look at 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. JavaScript is notorious for having an abundance of parentheses in its code, so that’s the aspect of syntax we’ll be focusing on. 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 three situations of erroneous syntax.
The first is when there’s 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’s 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 JavaScript code and ensures that there are no brace-related syntax errors? 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 pop the top element in the stack and inspect it. We then analyze:
-
If the item we popped (which is always an opening brace) does not match the current closing brace, it means we’ve encountered Syntax Error Type #3.
-
If we couldn’t pop an element because the stack was empty, that means the current closing brace doesn’t have a corresponding opening brace beforehand. This is Syntax Error Type #2.
-
If the item we popped is a corresponding match for the current closing brace, it means we’ve successfully closed that opening brace, and we can continue parsing the line of JavaScript code.
-
-
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 pop 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 top element of the stack, it means we can continue with our algorithm without throwing any errors.
Step 9: We move on, encountering a closing curly brace:
Step 10: We pop the top item from stack:
It’s an opening curly brace, so we’ve found a match with the current closing brace.
Step 11: We encounter a closing parenthesis:
Step 12: We pop the last element in the stack. It’s a corresponding match, so there are no errors so far.
Because 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 (relating to opening and closing braces).
Code Implementation: Stack-Based Code Linter
Here’s an implementation of the preceding algorithm. Note that we’re using our earlier implementation of the Stack class:
| | import stack |
| | |
| | |
| | class Linter: |
| | |
| | def __init__(self): |
| | self.stack = stack.Stack() |
| | |
| | def lint(self, text): |
| | while self.stack.read(): |
| | self.stack.pop() |
| | |
| | matching_braces = {"(": ")", "[": "]", "{": "}"} |
| | |
| | for char in text: |
| | |
| | if char in matching_braces.keys(): |
| | self.stack.push(char) |
| | |
| | elif char in matching_braces.values(): |
| | if not self.stack.read(): |
| | return char + " does not have opening brace" |
| | else: |
| | popped_opening_brace = self.stack.pop() |
| | |
| | if char != matching_braces.get(popped_opening_brace): |
| | return char + " has mismatched opening brace" |
| | |
| | # If we get to the end of line, and the stack isn't empty: |
| | if self.stack.read(): |
| | return self.stack.read() + " does not have closing brace" |
| | |
| | # Return True if line has no errors: |
| | return True |
The import stack allows our code to use our own stack implementation from above, as we saved it in a file called stack.py.
As soon as we create an instance of the Linter class, we create a stack that our algorithm can use. This is accomplished with the following code:
| | def __init__(self): |
| | self.stack = stack.Stack() |
The main linting algorithm takes place within the lint method, which accepts a string of JavaScript code and assigns it to a variable called text.
The very first thing we do is ensure that the stack is empty, as it still may have data in it from a previous linting. We accomplish this by popping data from the stack until there’s no data left:
| | while self.stack.read(): |
| | self.stack.pop() |
We then define what we consider to be sets of matching brackets:
| | matching_braces = {"(": ")", "[": "]", "{": "}"} |
We’re now up to the main part of the algorithm, which runs using a loop that analyzes each character of text, one at a time:
| | for char in text: |
If the character we’re up to is an opening brace, we push it onto the stack:
| | if char in matching_braces.keys(): |
| | self.stack.push(char) |
If the current character is not an opening brace, we then check to see if it’s perhaps a closing brace:
| | elif char in matching_braces.values(): |
If it is, we then consider a couple of possibilities. We first check to see if there’s anything on the stack. If there isn’t, we trigger Syntax Error #2:
| | if not self.stack.read(): |
| | return char + " does not have opening brace" |
If there is something on the stack, we pop it off and check to see if it’s a matching opening brace. If it isn’t, we trigger Syntax Error #3:
| | else: |
| | popped_opening_brace = self.stack.pop() |
| | |
| | if char != matching_braces.get(popped_opening_brace): |
| | return char + " has mismatched opening brace" |
The loop continues this way until it processes the entire text.
However, we’re not quite done. We still have to check whether the stack contains anything, because if it does, it means we have a stray opening brace that was never closed. This, again, is Syntax Error #1:
| | if self.stack.read(): |
| | return self.stack.read() + " does not have closing brace" |
At the end of our method we return True if we process the entire text and don’t encounter any errors.
Here’s some sample code to run our linter:
| | linter = Linter() |
| | linter.lint("(var x = 2;") |
This example will trigger Syntax Error #1 since the opening parenthesis has no closing parenthesis.
In this example, we used a stack to implement our linter with a neat algorithm. But if a stack actually uses an array under the hood, why bother with a stack? Couldn’t we have accomplished the same task using an array?
