Stack: Making a brackets validator

Today we will make a simple brackets validator using Stack data structure.

So let’s start!

As an example let’s think (a+b) is an expression; In this expression, we need to verify some rules.

1. If the open bracket exists in the expression then make sure to close bracket should exist after the open bracket.
2. Same for the close bracket, If the close bracket exists then make sure to open bracket should exist before the close bracket.
3. If the open bracket is ( then close bracket should ) not } or ].

Sound’s complex, but it is very easy when we use Stack.

So, what is the stack?

Stack is LIFO (Last in first out) like structure. In stack, the first item will pop out at the end and the last item will pop out first. Imagine a stack of books. When we take a book from the top, we are taking out a book that was put at the last.

And here is the following image of the stack data structure.

OK, let’s store (a+b) on the stack. It has five elements: (, a, +, b, and ). After putting five elements on the stack, It looks like the following image.

Let’s write some code. We can implement the Stack data structure by writing a simple class

class Stack {
    constructor() {
        this.items = [];
        this.top = -1;
    }

    push(value) {
        this.top++;
        this.items.push(value);
    }

    pop() {
        this.top--;
        return this.items.pop();
    }

    current() {
        return this.items[this.top];
    }

    isEmpty() {
        return this.top === -1;
    }

    clear() {
        this.top = -1;
        this.items = [];
        return this;
    }
}

This class has some methods and properties. So let’s know about those methods.

1. Using push() method, we can store an element into stack and increment the top value.
2. pop() method will remove and return last element of stack and also decrement value of top.
3. If you need current value of stack then you can get it by calling current() method.
4. To check if the stack is empty or not you can simply call isEmpty() method.
5. By calling clear() method, stack will be cleared.

OK, Let’s implement it into our application. We will use (a+b)} for our testing expression.

const text = '(a+b)}';
const arrayOfText = text.split('');
const stack = new Stack()
const bracketsPair = {
            ')': '(',
            '}': '{',
            ']': '['
        }
let errorIndex = undefined;

function check() {
          for (const [index, char] of arrayOfText.entries()) {
    // Since, we are only concerned about (,{,[
              if (char.match(/\(|\{|\[/)) {
                  stack.push(char);
                  continue;
              }
              if (char.match(/\)|\}|\]/)) {
                  if (bracketsPair[char] !== stack.pop()) {
                      errorIndex = index;
                      break;
                  }
              }
          }
          if (!stack.isEmpty() && !errorIndex) {
              errorIndex = (text.length - 1);
          }
      }

So let’s see what happens on each iteration of for loop

1^st iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = ['(']
errorIndex = undefined;

2^nd iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = ['(']
errorIndex = undefined;

3^rd iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = ['(']
errorIndex = undefined;

4^th iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = ['(']
errorIndex = undefined;

5^th iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = []
errorIndex = undefined;

6^th iteration

text = '(a+b)}';
arrayOfText = ['(', 'a', '+', 'b', ')', '}']
stack = []
errorIndex = 5;

Explanation of each iteration

1^st iteration

Our first character is the (, So it passes the first if statement and is pushed into the stack. Then continue to the next iteration.

2^nd iteration

The 2^nd character is a and it fails on the first if statement. So it moves on to the second if statement and it also fails here as well.

3^rd iteration and 4^th iteration

The third and fourth character is + and b and both of them follows the rule of the 2^nd iteration.

5^th iteration

In this iteration, first if statement fails but the next if statement is passed. Here popped out an item from the Stack and compare it with its pairs. In this iteration current character pairs are: ( and the popped item is (. Hooray, it matches! Let’s go next iteration.

6^th iteration

This is the last iteration of our for loop. And current character is }. So as you know its fails of the first if statement and passes the second if statement. Since our stack is empty. So pop out value is undefined and current character pairs are {. And here we found an error since undefined and { are not equal. Then update the value of errorIndex value to the current index.

So let’s see a basic demo app using Vue.js

You can find it here.