Last active
August 10, 2024 11:08
-
-
Save jcubic/4dd735dc31829ee69ce30ea4640c6fd8 to your computer and use it in GitHub Desktop.
Parentheses matching in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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