Check for valid parenthesis
Stacks
JavaScript
Problem:
Given an expression string containing the bracket characters {, }, (, ), [, and ], check whether the expression is valid. A valid expression must have matching pairs of brackets and maintain the correct order.
Example:
Input String: ‘{[()]}’
Output: TRUE
The output is TRUE because all the brackets are properly closed.
Input String: ‘{[(])}’
Output: FALSE
The output is FALSE because the bracket pairs are not closed in the correct order.
Input String: ‘[5 * (6 + 7)]’
Output: TRUE
The output is TRUE because all the brackets are properly closed.
Input String: ‘5 + [7 * (8 + 5])’
Output: FALSE
The output is FALSE because the square bracket is closed before the parenthesis.
Algorithm:
In this problem, we need to ensure that each opening bracket is closed by the corresponding type of closing bracket and that the brackets are closed in the correct order. Additionally, every closing bracket must have a matching opening bracket.
Steps:
- Loop through the characters in the expression and push all opening brackets onto the stack.
- When encountering a closing bracket, check if the opening bracket at the top of the stack corresponds to it.
- If a matching opening bracket is found at the top of the stack, remove it and continue the loop.
- If no matching opening bracket is found, the brackets are not properly closed, and the expression is invalid.
- At the end of the loop, if the stack is not empty, it indicates that there are unmatched opening brackets, so the expression is invalid.
Solution & Visualize:
The animation/visualization below illustrates the algorithm. Feel free to experiment with different input values.
Result
Code
Input:
Output:
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
let expression = args[0];
const stack = new Stack(
[],
{
name: 'Stack',
description: 'This stack is used to hold the brackets.'
}
);
let bracketMapping = {
')': '(',
']': '[',
'}': '{'
};
for (let i = 0; i < expression.length; i++) {
animatorModule.displayComment(
'Loop through the expression and push all opening brackets onto the stack. <br>'
+ highlightCharacter(expression, i),
500
);
char = expression[i];
charToMatch = bracketMapping[char] ?? null;
if (charToMatch) {
animatorModule.displayComment(
'When a closing bracket is encountered, pop the top element from the stack. <br>'
+ highlightCharacter(expression, i),
500
);
if (stack.isEmpty() || stack.pop() !== charToMatch) {
animatorModule.displayComment(
'There is no corresponding opening bracket, so the expression is invalid. <br>'
+ highlightCharacter(expression, i),
1000
);
break;
} else {
animatorModule.displayComment(
'There is a matching opening bracket. <br>'
+ highlightCharacter(expression, i),
1000
);
}
} else {
if (Object.values(bracketMapping).includes(char)) {
stack.push(char);
}
}
}
let result = stack.isEmpty() ? 'TRUE' : 'FALSE';
animatorModule.displayOutput(result);
if (stack.isEmpty()) {
animatorModule.displayComment(
'It is valid expression.',
500
);
} else {
animatorModule.displayComment(
'The expression has unmatched brackets, so it is invalid.',
500
);
}
return result;
}
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
}
})();