Стеки и очереди позволяют использовать эффективные алгоритмы Стеки и очереди - это структуры данных, ценность которых определяется алгоритмами, которые они открывают. Реальные проблемы редко требуют создания стека, однако многие задачи эффективно решаются только при использовании этих структур. Их ценность заключается не в самих структурах, а в том, как они позволяют принимать эффективные решения.
Проверка скобок как вариант использования канонического стека Для правильной последовательности скобок требуется, чтобы каждый открывающий символ был закрыт соответствующим типом в правильном порядке. В языках программирования есть несколько типов скобок — фигурные скобки, круглые скобки в скобках, квадратные скобки и угловые скобки для обобщений — и их порядок должен быть правильным. Автоматы Pushdown со стековой памятью моделируют этот синтаксический анализ, но простая проверка на основе стека отражает основную идею.
Простая реализация на C# со стеком и переключателем Используя систему.Коллекции.Generic.Stack, выполните итерацию строки и вставляйте открывающие скобки по мере их появления. При обнаружении закрывающего символа выполните сбой, если стек пуст или если открывающееся окно не соответствует типу закрывающего; в противном случае продолжайте. После обработки всех символов результат будет достигнут только в том случае, если стек пуст, при этом убедитесь, что не осталось незакрытых скобок.
Модульные тесты управляют обработкой крайних случаев В тестовом проекте используются типичные и граничные сценарии: слишком много начальных значений, слишком много конечных значений, правильно подобранные пары, пустая строка и строки, содержащие символы без скобок. Чтобы избежать повторяющихся утверждений, вспомогательный метод упрощает тестовый код. Обнаружение ошибок в неожиданных символах приводит к добавлению ветви по умолчанию, которая отклоняет любой символ, не заключенный в скобки, после чего тесты проходят успешно.
СУХОЙ рефакторинг со словарем сопоставления скобок Дублирующиеся ветви переключателей для каждого типа скобок заменяются словарем, сопоставляющим открывающие символы с соответствующими им доводчиками. Если символ является открывающей клавишей, нажмите на нее; в противном случае убедитесь, что стек не пуст, откройте его и убедитесь, что сопоставленный доводчик соответствует текущему символу, если он не совпадает. Это переписывание сокращает и проясняет код, сохраняет поведение и делает добавление новых типов скобок таким же простым, как обновление отображения.
Расширяемость и Производительность Переработанный подход может работать медленнее при сканировании коллекции и поиске в ней, в то время как исходный вариант с постоянными сравнениями работает быстрее. Чистый, расширяемый код не всегда является наиболее эффективным, поэтому правильный выбор зависит от рабочей нагрузки. Для путей, критически важных для производительности, можно сгенерировать оптимизированный переход на основе сопоставления, в то время как обычный код может быть более удобным для чтения и сопровождения.