Сбалансированные скобки
maximsidorovПроверка сбалансированных скобок
В данном примере рассматривается реализация алгоритма проверки сбалансированности квадратных скобок в строке, а также генерация случайных последовательностей скобок для тестирования.
Введение
Алгоритм проверки сбалансированных скобок — это классическая задача в программировании, которая используется для проверки корректности вложенных структур. Он применяется при анализе синтаксиса выражений, проверке корректности структуры HTML/XML-документов и в других случаях, где требуется соответствие открывающих и закрывающих элементов.
В данном случае реализована проверка последовательности квадратных скобок [ и ]. Алгоритм работает следующим образом:
- При встрече открывающей скобки
[счетчик увеличивается. - При встрече закрывающей скобки
]счетчик уменьшается. - Если счетчик становится отрицательным, это означает наличие лишней закрывающей скобки, и строка считается некорректной.
- По завершении прохода по строке счетчик должен быть равен нулю для корректной последовательности.
Помимо основной функции проверки, реализована функция генерации случайной последовательности из n пар скобок, которую можно использовать для тестирования алгоритма.
# Установка пакета Printf (если еще не установлен)
import Pkg; Pkg.add(["Printf", "Random"])
Основная часть
Функция проверки баланса скобок
Функция balancedbrackets(str) принимает на вход строку и проверяет, правильно ли расставлены скобки [ и ].
Логика работы:
- Для каждой открывающей скобки
[увеличивается счётчикi. - Для каждой закрывающей
]— уменьшается. - Если значение счётчика становится отрицательным, значит, встречена лишняя закрывающая скобка, и функция возвращает
false. - После окончания просмотра строки, если значение счётчика равно нулю, скобки сбалансированы — возвращается
true.
Пример поведения:
"[]"→true"]["→false"[[[]]]"→true"[]""]][["→false
# Подключение модуля Printf для форматированного вывода
using Printf
using Random
"""
Функция `balancedbrackets` принимает строку и проверяет,
сбалансированы ли в ней квадратные скобки.
Это делается путем подсчета:
- при встрече '[' увеличиваем счетчик (i += 1),
- при встрече ']' уменьшаем счетчик (i -= 1).
Если счетчик уходит в минус — слишком много закрывающих скобок.
В конце проверяем, что счетчик равен 0.
"""
function balancedbrackets(str::AbstractString)
# Инициализируем счетчик
i = 0
# Проходим по каждому символу строки
for c in str
# Увеличиваем счетчик, если открытая скобка
if c == '['
i += 1
# Уменьшаем, если закрытая
elseif c == ']'
i -= 1
end
# Если счетчик стал отрицательным — лишняя закрывающая скобка
if i < 0
return false
end
end
# Возвращаем true, только если все скобки нашли пару
return i == 0
end
Функция генерации случайных скобочных последовательностей
Функция brackets(n) генерирует строку из n пар скобок в случайном порядке.
Как это работает?
"[]" ^ nсоздаёт строку"[[][]...]"(n раз повторённый шаблон[])collect(...)превращает её в массив символовshuffle(...)произвольно перемешивает элементыjoin(...)снова собирает всё в одну строку
"""
Функция `brackets(n)` создает строку из n пар случайно перемешанных скобок '[' и ']'.
Сначала создается коллекция из n пар символов ("[]" repeated n times),
потом она преобразуется в массив символов и перемешивается функцией shuffle().
Затем результат объединяется в строку с помощью join().
"""
brackets(n::Integer) = join(shuffle(collect(Char, "[]" ^ n)))
Основная логика программы:
Для каждого числа от 0 до 8:
1. Генерируется случайная строка скобок длины 2*i (i пар).
2. Вызывается функция balancedbrackets() для проверки баланса.
3. Результат выводится в форматированном виде:
- сама строка
- результат проверки ("pass" / "fail").
for (test, pass) in map(x -> (x, balancedbrackets(x)), collect(brackets(i) for i = 0:8))
@printf "%22s %10s\n\n" test pass ? "pass" : "fail"
end
Заключение
Мы рассмотрели реализацию и применение алгоритма проверки сбалансированности квадратных скобок на языке Julia.
Что удалось сделать:
- Реализована функция
balancedbrackets(), которая проверяет, правильно ли расставлены скобки. - Написана вспомогательная функция
brackets(), создающая случайные скобочные строки для тестирования. - Проведено автоматическое тестирование для нескольких значений и продемонстрирован вывод.
Этот пример важен для понимания принципов анализа структур данных и может быть полезен при работе с парсерами, проверке синтаксиса и других задачах, где требуется соблюдение парности открывающих/закрывающих элементов.
Пример разработан с использованием материалов Rosetta Code