Перевод статьи “How to Match Parentheses in JavaScript without Using Regex”.
При написании интерпретатора Lisp (точнее, его диалекта — Scheme) я решил включить поддержку квадратных скобок. Дело в том, что в некоторых книгах по Scheme они используются наравне с круглыми. Но я не хотел слишком усложнять парсер, поэтому не стал проверять, совпадают ли скобки в парах.
В моем интерпретаторе Lisp скобки можно было бы смешать следующим образом:
(let [(x 10]) [+ x x)]
Приведенный выше код — это пример S-выражения, в котором есть токены — последовательности символов со значением (например, let или число 10) — и круглые и квадратные скобки. Но этот код невалиден из-за того, что пары круглых и квадратных скобок не совпадают.
(let [(x 10)] [+ x x])
А вот это — правильный синтаксис Lisp (если скобки поддерживаются). Открывающие круглые скобки всегда совпадают с закрывающими круглыми скобками, а открывающие квадратные скобки всегда совпадают с закрывающими квадратными.
В этой статье я покажу, как можно определить, является ли входное сообщение валидным S-выражением, т.е. таким, как во втором примере, а не в первом.
Мы также разберемся с такими случаями, как этот:
(define foo 10))))
Здесь вы видите недопустимый синтаксис, в котором закрывающих скобок больше, чем открывающих.
Проще говоря, мы будем определять, совпадают ли пары открывающих и закрывающих символов (), [] и {} внутри строки типа «[foo () {bar}]».
Решение этой задачи может пригодиться при реализации синтаксического анализатора Lisp, но вы можете использовать его и для других целей (например, для валидации или для вычисления математических выражений). Это также хорошее упражнение.
Примечание. Для понимания этой статьи и кода в примерах вам не нужно ничего знать о Lisp.
Использование стека
Вы можете подумать, что самый простой способ решить эту задачу — использовать регулярные выражения (RegExp). Возможно, для простых случаев это подойдет, но вскоре выражение станет слишком сложным и будет скорее создавать проблемы, чем решать их.
На самом деле, самый простой способ сопоставления открывающих и закрывающих символов — это использование стека. Стек — это простейшая структура данных. У нас есть две основные операции: push — для добавления элемента в стек и pop — для удаления элемента.
Это похоже на стопку книг. Последняя книга, которую вы положили в стопку, будет первой, которую вы уберете.
С помощью стека легче обрабатывать (парсить) символы, которые имеют начало и конец, например XML-теги или простые круглые скобки.
Например, у нас есть такой XML-код:
<element><item><sub-item>text</sub-item></item></element>
Когда мы используем стек, последний тег, который мы открываем (например, внутренний <sub-item>), всегда будет первым, который нам нужно закрыть (если XML валиден).
То есть мы можем добавлять в стек (push) элемент <sub-item>, когда открываем его, и изымать из стека (pop), когда необходимо этот элемент закрыть. Все, что нам нужно, — следить за тем, чтобы последний элемент в стеке, который всегда является открывающим тегом, совпадал с закрывающим.
Та же логика работает и со скобками.
Обратите внимание, что самозакрывающиеся теги XML можно пропускать, так как они открываются и автоматически закрываются.
Массивы в JavaScript имеют методы push и pop, поэтому их можно использовать как стек. Но удобнее создать абстракцию в виде класса, чтобы добавить дополнительные методы, такие как top() и is_empty(), которые легче читать. Впрочем, даже если бы мы не добавляли новые методы, всегда лучше создавать подобные абстракции, потому что это делает код проще и легче для чтения.
class Stack {
#data;
constructor() {
// creating new empty array as hidden property
this.#data = [];
}
push(item) {
// push method just use native Array::push()
// and add the item at the end of the array
this.#data.push(item);
}
len() {
// size of the Stack
return this.#data.length;
}
top() {
// sice the items are added at the end
// the top of the stack is the last item
return this.#data[this.len() - 1];
}
pop() {
// pop is similar to push and use native Array::pop()
// it removes and returns the last item in array
return this.#data.pop();
}
is_empty() {
// this comment shortcut !0 is true
// since 0 can is coerced to false
return !this.len();
}
}
В приведенном выше коде используется класс ES6 (ES2015) и приватные свойства ES2022.
Алгоритм сопоставления скобок
Теперь я опишу шаги, необходимые для парсинга круглых скобок.
Нам нужен цикл, который будет проходить через каждый токен — и лучше всего, если все остальные токены будут удалены перед обработкой.
Когда у нас есть открывающая скобка, мы должны поместить этот элемент в стек. Когда у нас есть закрывающая скобка, нам нужно проверить, совпадает ли последний элемент в стеке с тем, который мы обрабатываем.
Если элемент совпадает, мы удаляем его из стека. В противном случае мы перепутали скобки и должны выбросить исключение.
Если у нас есть закрывающая скобка, но в стеке ничего нет, нам также нужно выбросить исключение, потому что нет открывающей скобки, которая бы совпадала с закрывающей.
После проверки всех символов (токенов), если в стеке что-то осталось, это означает, что мы не закрыли все скобки. Но это не страшно, ведь пользователь может находиться в процессе написания. Поэтому в этом случае мы возвращаем false, а не исключение.
Если стек пуст, мы возвращаем true. Это означает, что у нас есть полное выражение. Если бы это было S-выражение, мы могли бы использовать парсер для его обработки, и нам не пришлось бы беспокоиться о невалидных результатах.
Исходный код
function balanced(str) {
// pairs of matching characters
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 our matching characters
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 matching characters 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 empty
throw new Error(`Syntax error: not matched closing ${token}`);
}
}
return stack.is_empty();
}
Приведенный выше код был реализован как часть моего парсера S-выражений, но единственное, что я использовал из той статьи, — это функция tokenize(), которая разбивает строку на токены (где токен — это один объект, например число 123 или строка «hello»). Если вы хотите обрабатывать только символы, вы можете использовать str.split(''), тогда токены будут представлять собой массив символов.
Этот код намного проще, чем парсер S-выражений, потому что нам не нужно обрабатывать все токены. Но, используя функцию tokenize() из упомянутой выше статьи, мы сможем проверять вводимые данные:
(this "))))")
Полный исходный код (включая функцию tokenize()) можно найти на GitHub.
Резюме
Не стоит даже начинать обрабатывать выражения, содержащие открывающие и закрывающие символы, с помощью регулярных выражений. На StackOverflow есть обсуждение этой темы: RegEx match open tags except XHTML self-contained tags.
Сопоставление скобок представляет собой точно такую же проблему, как и парсинг HTML. Как видно из приведенного выше кода, проблема решается проще, если мы используем стек.
Возможно, мы могли бы написать регулярное выражение, которое проверяло бы, есть ли в последовательности символов совпадающие круглые скобки. Но это быстро усложнится, если в качестве токенов (последовательностей символов) будут выступать строки, как в S-выражениях, а круглые скобки внутри этих строк будут игнорироваться. А ведь подобную задачу можно решить довольно просто, если применить более подходящие инструменты.
Лично я люблю регулярные выражения, но, если вы намерены их применить, всегда стоит задуматься, будет ли это наилучшим решением.
