Stacks Binary Trees

Find the index of closing bracket for a given opening bracket

Stacks
JavaScript

Problem:

Given a string containing square brackets, if the index of an opening bracket is provided, find the index of its corresponding closing bracket. Assume that only square brackets ([ and ]) are used.

Example:

Input string: ‘[X[YZ][AB]][MN]’

Input (Opening bracket Index): 0

Output: 10

The closing bracket at index 10 matches the opening bracket at index 0.

Input (Opening bracket Index): 6

Output: 9

The closing bracket at index 9 matches the opening bracket at index 6.

Algorithm:

To solve this, we will start from the given index of the opening bracket and push brackets onto the stack. When we encounter a closing bracket, we pop the opening bracket from the stack. If the stack becomes empty after popping, the current index will be the index of the closing bracket.

Steps:

  1. Loop through the characters starting from the index of the opening bracket.
  2. Push all opening brackets onto the stack.
  3. When a closing bracket is encountered, pop the top element from the stack. If the stack is empty after this operation, the current index will be the index of the closing bracket.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm to reverse a string works. Feel free to experiment by changing the input strings.

Result
Code

Input:

This is the custom help text for this input

Output:

   
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
    let string = args[0];
    let startIndex = parseInt(args[1]);
    let endIndex = -1;

    if (string[startIndex] !== '[') {
        animatorModule.displayComment(
            '<span class="sv-comment-error">Error: There is no opening bracket ([) at the given index.</span>',
            15000
        );
    }

    const stack = new Stack(
        [],
        {
            name: 'Stack',
            description: 'This stack will hold the opening brackets.'
        }
    );

    for (var i = startIndex; i < string.length; i++) {
        animatorModule.displayComment(
            'Loop through the characters and push all opening brackets onto the stack. <br>'
            + highlightCharacter(string, i),
            500
        );
        if (string[i] == '[') {
            stack.push('[');
        }

        if (string[i] == ']') {
            animatorModule.displayComment(
                'When a closing bracket is encountered, pop the top element from the stack. <br>'
                + highlightCharacter(string, i),
                500
            );

            // If stack is empty, then the brackets are not valid
            if (stack.isEmpty()) {
                animatorModule.displayComment(
                    '<span class="sv-comment-error">Error: The string does not contain the valid pair of brackets.</span>',
                    15000
                );
                return;
            }

            stack.pop();

            if (stack.isEmpty()) {
                animatorModule.displayComment(
                    'If stack is empty then we have found the end index.',
                    1500
                );
                endIndex = i;
                break;
            }
        }
    }

    animatorModule.displayOutput(endIndex);
    animatorModule.displayComment('');
    return endIndex;
}
                                        
class Stack {
    metaData = {
        'name': 'Stack',
        'description': '',
        'animation_duration': 1500,
    }

    constructor(initialData, metaData) {
        this.initialData = [...initialData];
        this.metaData = Object.assign({}, this.metaData, metaData);

        this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
        this.stackId = this.stackDisplayer.display();
    }

    getStackData() {
        return this.initialData;
    }

    push(value) {
        this.initialData.push(value);

        // Perform the animation
        animatorModule.performPushAnimation(this.stackId, value);
    }

    pop() {
        if (this.initialData.length == 0) return;

        const value = this.initialData.pop();

        // Perform the animation
        animatorModule.performPopAnimation(this.stackId, value);

        return value;
    }

    top() {
        if (this.initialData.length == 0) return;

        const value = this.initialData[this.initialData.length - 1];

        return value;
    }

    isEmpty() {
        return this.initialData.length === 0;
    }
}
                                        
class StackDisplayer {
    constructor(initialData, metaData) {
        this.initialData = initialData;
        this.metaData = metaData;
    }

    display() {
        // Display stack on the screen
        const stackTemplate = document.getElementById('stack-template');
        const clone = stackTemplate.content.cloneNode(true);
        const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;

        // Add an unique ID to the clone
        const stackWrapperId = 'stack-' + stackCount;
        const stackWrapper = clone.querySelector('.stack-wrapper');
        stackWrapper.id = stackWrapperId;

        // Add initial stack items
        const stackElement = clone.querySelector('.stack');
        while(this.initialData.length) {
            stackElement.insertAdjacentHTML(
                'beforeend',
                '<div class="stack-item">'+ this.initialData.pop() +'</div>'
            )
        }

        clone.querySelector('.stack-description h4')
             .textContent = this.metaData.name;
        clone.querySelector('.stack-description p')
             .textContent = this.metaData.description;

        document.getElementById('stack-visualizer')
                .appendChild(clone);

        return stackWrapperId;
    }
}
                                        
class AnimationList {
    animations = [];

    length() {
        return this.animations.length;
    }

    push(animation) {
        this.animations.push(animation);
    }

    shift() {
        return this.animations.shift();
    }
}

let animatorModule = (function() {
    let animations = new AnimationList();
    let animationsRunning = false;
    let animationSpeed = 1200;

    function getMoveDownAnimation(animation) {
        let topElement = animation.stackElement.children[0];

        let distance = animation.stackElement.offsetHeight;
        if (topElement) {
            distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().height
                        - 2; // Margin bottom
        }

        let moveDownAnimation = [
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            (0.2 * distance) +  'px',
            (0.37 * distance) +  'px',
            (0.55 * distance) +  'px',
            (0.7 * distance) +  'px',
            (0.87 * distance) +  'px',
            distance  + 'px',
            distance  + 'px'
        ];

        return moveDownAnimation;
    }

    function getMoveUpAnimation(animation) {
        let topElement = animation.stackElement.children[0];
        let distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y;

        let moveUpAnimation = [
            (distance - 0.95 * distance) +  'px',
            (distance - 0.87 * distance) +  'px',
            (distance - 0.7 * distance) +  'px',
            (distance - 0.55 * distance) +  'px',
            (distance - 0.37 * distance) +  'px',
            (distance - 0.2 * distance) +  'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px'
        ];

        return moveUpAnimation;
    }

    function pushAnimate(animation) {
        animation.pushElement.textContent = animation.value;

        let pushAnimationKeyFrames = {
            // 25% - Show element
            opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
            left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
            top: getMoveDownAnimation(animation),
            offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
        };

        let duplicateElement = animation.pushElement.cloneNode(true);
        duplicateElement.classList.remove('hidden');

        // TODO: Increase the height of the stack before pushing

        let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);

        return new Promise((resolve) => {
            return pushAnimation.finished.then(() => {
                animation.stackElement.prepend(duplicateElement);
                resolve(`Push Animation completed!`);
            });
        })
    }

    function popAnimate(animation) {
        let popAnimationKeyFrames = {
            bottom: getMoveUpAnimation(animation),
            left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
            offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
        };

        let topElement = animation.stackElement.children[0];

        let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
        // The animation is not smooth
        // So remove the item before animation is completed
        setTimeout(() => {
            topElement.remove();
            animation.popElement.textContent = topElement.textContent;
        }, animationSpeed - 200);

        return new Promise((resolve) => {
            return popAnimation.finished.then(() => {
                // topElement.remove();
                // animation.popElement.textContent = topElement.textContent;
                resolve(`Pop Animation completed!`);
            });
        })
    }

    function displayCommentAnimate(animation) {
        return new Promise((resolve) => {
            document.getElementsByClassName('sv-comment')[0]
                    .innerHTML = animation.value;

            setTimeout(() => {
                resolve('Comment displayed!');
            }, animation.timeout);
        })
    }

    function displayOutputAnimate(animation) {
        return new Promise((resolve) => {
            let outputELement = document.getElementById('final-output');
            outputELement.innerHTML = animation.value;
            resolve('Output displayed!');
        })
    }

    function runSingleAnimation(animation) {
        switch (animation.type) {
            case 'push':
                return pushAnimate(animation);
                break;
            case 'pop':
                return popAnimate(animation);
                break;
            case 'display-comment':
                return displayCommentAnimate(animation);
                break;
            case 'display-output':
                return displayOutputAnimate(animation);
                break;
        }
    }

    function runAnimations() {
        if (animationsRunning) return;

        animationsRunning = true;
        // Perform the animations one after the other
        let animation = animations.shift();
        runSingleAnimation(animation)
            .then(() => {
                animationsRunning = false;
                if (animations.length()) {
                    runAnimations();
                }
            });
    }

    function getStackElements(stackId) {
        let stackWrapper = document.getElementById(stackId);
        return {
            stackElement: stackWrapper.getElementsByClassName('stack')[0],
            pushElement: stackWrapper.getElementsByClassName('push-element')[0],
            popElement: stackWrapper.getElementsByClassName('pop-element')[0]
        }
    }

    let performPushAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'push', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    let performPopAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'pop', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    /**
     * Set the animation duration.
     *
     * @param flot speed Duration in seconds (1, 2.5...)
     */
    let setAnimationSpeed = function (speed) {
        animationSpeed = speed * 1000;
    }

    let displayComment = function (comment, timeout = 0) {
        let animationObject = {
            type: 'display-comment',
            value: comment,
            timeout: timeout
        };

        animations.push(animationObject);
        runAnimations();
    }

    let displayOutput = function (output) {
        let animationObject = {
            type: 'display-output',
            value: output
        };

        animations.push(animationObject);
        runAnimations();
    }

    let clearAnimations = function () {
        animations = new AnimationList();
        animationsRunning = false;
    }

    return {
        performPushAnimation: performPushAnimation,
        performPopAnimation: performPopAnimation,
        setAnimationSpeed: setAnimationSpeed,
        displayComment: displayComment,
        displayOutput: displayOutput,
        clearAnimations: clearAnimations
    }
})();