Skip to content

Instantly share code, notes, and snippets.

@jcubic
Last active August 10, 2024 11:08
Show Gist options
  • Save jcubic/4dd735dc31829ee69ce30ea4640c6fd8 to your computer and use it in GitHub Desktop.
Save jcubic/4dd735dc31829ee69ce30ea4640c6fd8 to your computer and use it in GitHub Desktop.
Parentheses matching in JavaScript
try {
console.log(balanced('()'));
console.log(balanced('(x()x)'));
console.log(balanced('(this "))))")'));
console.log(balanced('(multiple) (expressions) (in) (one) (string)'));
console.log(balanced('(x()x'));
console.log(balanced('{foo [bar]}'));
console.log(balanced('(x([)]x'));
} catch (e) {
console.log(e.message);
}
// Copyright (C) 2024 Jakub T. Jankiewicz <https://jcubic.pl/me>
// Released under MIT license
class Stack {
#data;
constructor() {
this.#data = [];
}
push(item) {
this.#data.push(item);
}
len() {
return this.#data.length;
}
top() {
return this.#data[this.len() - 1];
}
pop() {
return this.#data.pop();
}
is_empty() {
return !this.#data.length;
}
}
const tokens_re = /("[^"\\]*(?:\\[\S\s][^"\\]*)*"|[()[\]{}]|\n|\s+|[^\s()]+)/
function tokenize(string) {
string = string.trim();
if (!string.length) {
return [];
}
return string.split(tokens_re).filter(token => token.trim());
}
function balanced(str) {
// pairs of matching brackets
const maching_pairs = {
'[': ']',
'(': ')',
'{': '}'
};
const open_tokens = Object.keys(maching_pairs);
const brackets = Object.values(maching_pairs).concat(open_tokens);
// we filter out what is not a bracket
// instead of tokenize you can use str.split('')
const tokens = tokenize(str).filter(token => {
return brackets.includes(token);
});
const stack = new Stack();
for (const token of tokens) {
if (open_tokens.includes(token)) {
stack.push(token);
} else if (!stack.is_empty()) {
// there are brackets on the stack
const last = stack.top();
// the last opening character needs to match
// the closing bracket we have
const closing_token = maching_pairs[last];
if (token === closing_token) {
stack.pop();
} else {
// the character don't match
throw new Error(`Syntax error: missing closing ${closing_token}`);
}
} else {
// this case when we have closing token but no opening one,
// becauase the stack is emtpy
throw new Error(`Syntax error: not matched closing ${token}`);
}
}
return stack.is_empty();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment