brackets_validator.js

const BRACKETS = ['{', '}', '(', ')', '[', ']']
let isValidByCount = (str) => {
	let bracketPosition = 0
	let bracketsAmountPerType = new Array(BRACKETS.length).fill(0)
	for (let char of str) {
		bracketPosition = BRACKETS.indexOf(char)
		if (bracketPosition > -1) bracketsAmountPerType[bracketPosition] += 1
	}
	for (let i = 0; i < BRACKETS.length; i+=2)
		if (bracketsAmountPerType[i] !== bracketsAmountPerType[i+1])
			return false
	
	return true
}

const isValidLookup = (str) => {
	let length = str.length, index = 0, bracketPosition = 0
	let result = true, leftFound = false, innerBrackets = []
	let processedRightBrackets = []
	for (let char of str) {
		bracketPosition = BRACKETS.indexOf(char)
		if (bracketPosition > -1) {
			if (!leftFound) leftFound = bracketPosition % 2 === 0
			if (!leftFound && (bracketPosition % 2 === 1)) {
				/* RIGHT FOUND */
				if (processedRightBrackets.indexOf(index) === -1) {
					return false
				}
			}
			else {
				let subResult = false
				for (let i = index + 1; i < length; i++) {
					if (processedRightBrackets.indexOf(i) > -1) continue
					else {
						let nextChar = str.charAt(i)
						let nextBracketPosition = BRACKETS.indexOf(nextChar)
						if (nextBracketPosition > -1) {
							if (nextBracketPosition === (bracketPosition + 1)) {
								if (innerBrackets.length > 0) {
									innerBrackets = innerBrackets
										.filter(i => i !== bracketPosition)
										.filter(i => i !== nextBracketPosition)
								}
								processedRightBrackets.push(i)
								subResult = true
								leftFound = false
								break
							}
							else innerBrackets.push(nextBracketPosition)
						}
					}
				}
				if (innerBrackets.length % 2 === 1) return false
				result = subResult
			}
		}
		// if (processedRightBrackets.length > length/2) break
		index++
	}
	return result
}

// const checkValidOptimise = (line) => isValidByCount(line) ? isValidLookup(line) : false

function isValid (str){
	const stack = []
	for (let chr of str) {
		if (stack[0] === chr) stack.shift()
		else if (chr === '{' || chr === '}') stack.unshift('}')
		else if (chr === '(' || chr === ')') stack.unshift(')')
		else if (chr === '[' || chr === ']') stack.unshift(']')
	}
	return !stack.length
}

let testCases = [
	["(foo)", true],
	["(f[o]{o})", true],
	["[(){}()()]", true],
	["(foo", false],
	["((fo(dsd)o))", true],
	["{f[o}o]", false],
	["{{f(dd)o}}o", true],
	["{{f(dd)o}}{}]o", false],
	["{{f(dd)o}}o]", false],
	["{{f}(dd)o}}od[]a[sda{}dw]", false]
]
// =========> SINGLE RUN <============
// testCases.forEach(item => console.log(isValidLookup(item[0])===item[1]))
// return

const testIterations = 10000
let counter = testIterations, timeStart = Date.now()
// console.log("=============== TEST BY COUNT ================")
// console.time('testCase_ByCount')
// while(counter--) testCases.forEach(isValidByCount)
// console.timeEnd('testCase_ByCount')
// console.log(`==================== END ${Date.now() - timeStart}ms =====================`)
// console.log("============ TEST BY CLOSE LOOK ==============")
// console.time('testCase_Lookup')
// counter = testIterations
// timeStart = Date.now()
// while(counter--) testCases.forEach(isValidLookup)
// console.timeEnd('testCase_Lookup')
// console.log(`==================== END ${Date.now() - timeStart}ms =====================`)
// console.log("============== TEST OPTIMISED ================")
// console.time('testCase_Optimised')
// counter = testIterations
// timeStart = Date.now()
// while(counter--) testCases.forEach(checkValidOptimise)
// console.timeEnd('testCase_Optimised')
// console.log(`==================== END ${Date.now() - timeStart}ms =====================`)

function isValid21 (str){
	const stack = []
	const length = str.length
	const lengthHalf = length * 0.5
	for (let i = 0; i < length; i++) {
		let chr = str[i]
		if (stack.length > lengthHalf) break;
		else if (stack[0] === chr) stack.shift()
		else if (chr === '{' || chr === '}') stack.unshift('}')
		else if (chr === '(' || chr === ')') stack.unshift(')')
		else if (chr === '[' || chr === ']') stack.unshift(']')
	}
	return !stack.length
}
let open1 = {'{': '}', '[': ']', '(': ')'}
let closed2 = {'}': true, ']': true, ')': true}
let isParenthesisMatching = (str) => {
	let stack = [];
	const lengthHalf = str.length * 0.5
	const open = open1
	const closed = closed2
	for (let char of str) {
		if (stack.length > lengthHalf) break;
		if (open[char]) {
			stack.push(char);
		} else if (closed[char]) {
			if (open[stack.pop()] !== char) return false;
		}
	}
	return stack.length === 0;
}

//
testCases.forEach(item => console.log(isValidLookup(item[0])))

testCases = testCases.map(item => item[0])

console.time('test')
counter = testIterations
while(counter--) testCases.forEach(isValidLookup)
console.timeEnd('test')

let tries = 300
let totalTime = 0
for (let i=0;i<tries;i++) {
	timeStart = Date.now()
	counter = testIterations
	while(counter--) testCases.forEach(isValidLookup)
	totalTime += Date.now() - timeStart
}

console.log(`Average after ${tries * testIterations} = ${totalTime/tries}ms`)