This is the 36th day of my participation in the First Text Challenge 2022.First challenge in 2022.

Data structure stack practice

The stack is rarely used in scenarios that require long-term retention of data, but is often used in various algorithms that process temporary data.

Let’s write a rudimentary JavaScript parser — a tool to check that JavaScript code is syntactically correct. Because JavaScript has a lot of syntax rules, it can be complicated. For simplicity’s sake, let’s just focus on the closing of parentheses, parentheses, square parentheses, and curly parentheses, which can be very frustrating to get wrong.

Before writing, analyze what happens when parentheses are syntactically incorrect. The categories are the following three.

The first is when there’s an open parenthesis and no close parenthesis.

(var x=2;
Copy the code

This goes to category 1.

And then there’s the case where there’s no open parenthesis but there’s a close parenthesis.

var x=2;)
Copy the code

This falls into category 2.

There is also a third class, where the close parenthesis type does not match the closest opening parenthesis before it, for example:

(var x=[1, 2, 3)];
Copy the code

In this case, although the parentheses and square brackets are paired, they are not in the right place, and the closest before the right parentheses is the left parentheses.

So how do you implement an algorithm that checks if the parentheses in a line of code are correct? It’s easy to use a stack.

Prepare an empty stack, then read each character of the code from left to right, and execute the following rules.

(1) If you read a character that is not a parenthesis (parenthesis, square parenthesis, curly parenthesis), ignore it and move on.

(2) If an open parenthesis is read, it is pushed onto the stack, meaning that a corresponding close parenthesis is needed to close it.

(3) If you read the close parenthesis, look at the element at the top of the stack and do the following analysis.

  • If there are no elements in the stack, you encounter a close parenthesis but no open parenthesis, a type 2 syntax error.
  • If you have data in the stack that doesn’t match the type of the close bracket you just read, that’s a class 3 syntax error.
  • If the top element of the stack is a matching open bracket, it is closed. Then you can pop it out, because you don’t need to remember it anymore.

(4) If a line of code is finished and data is left in the stack, it indicates that there is an open parenthesis and no close parenthesis matches it, which is a class 1 syntax error.

Let’s use the following code as an example to demonstrate this.

With an empty stack ready, you can start reading each character of your code from left to right.

Step 1: Start with the first character, which is an open parenthesis.

Step 2: Because it is an open parenthesis, push it onto the stack.

And then the var x =, none of them are parentheses, so they’re ignored.

Step 3: An open curly brace is encountered.

Step 4: Push it onto the stack.

Then ignore y:.

Step 5: An open square bracket is encountered.

Step 6: Push it on the stack as well.

And then ignore 1, 2, 3.

Step 7: This is the first time we see a close bracket, a close square bracket.

Step 8: Then check the element at the top of the stack and discover that it is an open square bracket. Because the right square bracket you just read matches it, pop the left square bracket.

Step 9: Continue, the next read is the close curly brace.

Step 10: Check that the last element on the stack happens to be a matching open curly brace. So I pop it out.

Step 11: Read a close parenthesis.

Step 12: Check the last element on the stack, which happens to be the pairing open parenthesis. I pop it out, leaving an empty stack.

At this point, the code is finished and the stack is empty, so our parser can conclude that the code has no syntax errors in parentheses.