Стеки. Анализ правильности скобочного выражения
Цели и задачи
- Цель по SMART: к концу урока научиться объяснять принцип работы стека и применять алгоритм анализа правильности скобочного выражения, содержащего круглые, квадратные и фигурные скобки, проверяя результат на тестовых примерах.
- Сформировать понимание стека как структуры данных, работающей по принципу LIFO: последний вошёл — первый вышел.
- Научиться пошагово моделировать обработку скобочного выражения и выявлять ошибку при преждевременном закрытии или наличии незакрытых скобок.
- Развивать умение переводить алгоритм в программу и проверять его на граничных случаях с использованием среды программирования.
- Формировать ответственное отношение к точности алгоритмических рассуждений и готовность аргументировать выбранное решение при работе в паре.
Планируемые результаты
Личностные
- Ученик осознаёт практическую значимость стеков для программирования, компиляторов, редакторов и обработки структурированных данных.
- Проявляет интерес к исследовательской проверке алгоритма и принимает необходимость тестирования программ на корректных и ошибочных примерах.
- Ответственно относится к точности записи алгоритма и к аргументированной оценке результата работы пары.
- Осознаёт связь темы с дальнейшим изучением алгоритмов, структур данных и профессиональной деятельностью в сфере информационных технологий.
Метапредметные
- Выделяет существенные признаки стека и сопоставляет их с последовательностью действий алгоритма.
- Планирует решение задачи, фиксирует промежуточное состояние стека и осуществляет самопроверку по критериям.
- Работает с информацией в виде текста, таблицы трассировки, схемы алгоритма и программного кода.
- Взаимодействует с одноклассником: распределяет роли, задаёт уточняющие вопросы и аргументирует вывод.
- Использует цифровую среду для запуска программы, анализа ошибок и сравнения результатов тестов.
Предметные
- Знать определение стека и принцип LIFO, а также операции добавления и извлечения элемента.
- Уметь проверять правильность скобочного выражения с одним или несколькими типами скобок.
- Уметь составлять трассировочную таблицу: символ, действие, содержимое стека, результат проверки.
- Уметь формулировать условие ошибки: закрывающая скобка не соответствует последней открывающей или стек не пуст в конце обработки.
- Владеть базовым алгоритмом и реализовывать его в программе с использованием строки и списка как модели стека.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный интерес к алгоритмам и оценивают, какие умения потребуются для дальнейшего обучения программированию.
- Понимают ценность аккуратного пошагового рассуждения при разработке программ.
- Принимают возможность ошибки как источник для анализа и улучшения алгоритма.
- Проявляют самостоятельность при выборе тестов и способа представления решения.
Регулятивные УУД
- Формулируют цель: научиться определять корректность скобочного выражения с помощью стека.
- Планируют последовательность действий: чтение символа, изменение стека, проверка соответствия, итоговый вывод.
- Осуществляют пошаговый контроль состояния стека и находят место возникновения ошибки.
- Сверяют программу с эталонным алгоритмом и корректируют код после анализа тестов.
- Оценивают результат по критериям правильности, полноты тестирования и объяснимости решения.
Познавательные УУД
- Моделируют работу абстрактной структуры данных на конкретном выражении.
- Сравнивают операции со стеком и действия с последовательностью скобок.
- Анализируют граничные случаи: пустая строка, одна пара скобок, лишняя закрывающая скобка, незакрытая открывающая скобка.
- Строят причинно-следственную связь между состоянием стека и выводом программы.
- Преобразуют словесное описание алгоритма в псевдокод и программную реализацию.
Коммуникативные УУД
- Распределяют роли в паре: исполнитель моделирует стек, контролёр проверяет каждый шаг.
- Формулируют вопросы о причинах изменения стека и корректности результата.
- Объясняют партнёру, почему последняя открытая скобка должна закрываться первой.
- Аргументированно принимают или отклоняют предложенный тестовый пример.
- Согласуют общий вывод и представляют его классу в краткой форме.
Подготовка учителя к уроку
- Подготовить презентацию или экранную схему со стеком в виде вертикального списка и обозначениями «поместить» и «извлечь».
- Распечатать карточки с выражениями трёх уровней сложности — по одной карточке на пару и несколько резервных экземпляров.
- Подготовить индивидуальный лист трассировки с колонками «символ», «действие», «стек», «результат».
- Подготовить лист с псевдокодом алгоритма и пропусками для ключевых условий — по одному на ученика.
- Открыть на компьютерах среду программирования; проверить запуск короткой программы на языке, изучаемом классом.
- Вывести на доску памятку: LIFO, операции push и pop, соответствия (), [], {}.
- Подготовить тестовый набор из корректных выражений: (), [], {[()]}, и ошибочных: (, ([)], )(, {[}.
- Распечатать критерии оценивания практической работы — по одному на ученика.
- Подготовить карточки самооценки «могу объяснить», «могу промоделировать», «могу написать программу» — по одной на ученика.
- Организовать работу за компьютерами парами, заранее определить номера компьютеров и порядок смены ролей.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в учебную деятельность и показать практическую проблему, для решения которой необходим стек.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и проверяет готовность компьютеров: "Здравствуйте, ребята. Сегодня мы будем не просто изучать новую структуру данных, а разберём задачу, которая встречается в компиляторах, редакторах кода и математических выражениях. Проверьте, что перед вами открыты тетрадь, ручка и рабочая среда программирования. Не запускайте код до моей команды." | Проверяют оборудование, открывают тетради и среду программирования, записывают дату. |
2 мин | Учитель выводит на экран выражения «{[()]}», «{[(])}» и «([». Учитель спрашивает: "Как программа может определить, что первое выражение правильное, второе содержит неправильный порядок закрытия, а в третьем не хватает закрывающей скобки? Можно ли решить задачу, сравнивая только количество скобок?" | Сравнивают выражения, предполагают: "Нужно учитывать порядок", "Одинаковое количество скобок ещё не гарантирует правильность", формулируют проблему урока. |
Завершение этапа: учитель подводит итог: "Мы увидели, что простой подсчёт скобок недостаточен: важно помнить, какая открывающая скобка была последней. Сегодня мы выясним, какая структура данных естественно хранит такую информацию."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: актуализировать знания о последовательностях, алгоритмах и условных операциях, необходимые для открытия нового способа решения.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель задаёт вопросы: "Что такое структура данных? Какие последовательности вы уже использовали в программах? Какая операция позволяет обратиться к элементу строки по его индексу?" Затем фиксирует на доске слова «последовательность», «элемент», «индекс», «условие». | Отвечают: "Структура данных хранит и организует данные", "Мы работали со строками и списками", "К элементу строки обращаются по индексу". |
3 мин | Учитель показывает последовательность действий с книгами: "Представьте стопку книг. Какую книгу мы возьмём первой, если не можем вытащить книгу из середины? Какую положим сверху? Запишите правило одной фразой." | Формулируют правило: "Последней положенная книга извлекается первой"; связывают его с принципом LIFO и записывают термин «стек». |
Запись в тетрадях
Стек — структура данных, в которой первым извлекается последний добавленный элемент. Принцип работы: LIFO — «последним вошёл, первым вышел». Основные операции: добавление элемента на вершину стека и извлечение элемента с вершины стека.
Завершение этапа: учитель подводит итог: "Мы вспомнили, что порядок действий имеет значение, и вывели модель стопки. Теперь проверим, как эта модель помогает анализировать скобки."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: сформулировать алгоритмическую проблему и совместно определить план её решения.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт парам карточку с выражением «{[()]}>» без последнего символа и говорит: "Подумайте в паре, что нужно хранить, когда мы читаем выражение слева направо. Не называйте пока готовый алгоритм — опишите информацию, которую нельзя потерять." | В парах обсуждают 1 минуту, записывают: "Нужно хранить открывающие скобки и их порядок"; один ученик представляет вывод пары. |
2 мин | Учитель организует приём «Снежный ком»: "Сначала каждая пара предлагает условие корректности, затем сравним формулировки. Как понять, что закрывающая скобка подходит? Что проверить после чтения всей строки?" | Формулируют план: открывающую скобку помещать в стек; закрывающую сравнивать с вершиной; после обработки стек должен быть пустым. Записывают цель урока. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "План решения у нас есть: читать строку, управлять стеком, проверять соответствие и сделать итоговый вывод. Теперь превратим этот план в точный алгоритм."
Этап 4. Открытие нового знания: алгоритм стека (10 мин)
Цель этапа: вывести и осознанно применить алгоритм проверки правильности скобочного выражения.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель показывает на экране выражение «{[()]}» и вертикальную модель стека: "Читаем строку слева направо. Если видим открывающую скобку, помещаем её в стек. Если видим закрывающую, сначала проверяем, пуст ли стек. Если пуст — ошибка. Если не пуст — извлекаем вершину и сравниваем пары: (), [], {}." Учитель демонстрирует первые четыре шага. | Заполняют таблицу трассировки: для «{» стек «{»; для «[» стек «{[»; для «(» стек «{[(»; для «)» извлекают «(», стек «{[». Формулируют: "Закрывается последняя открытая скобка". |
3 мин | Учитель продолжает разбор: "После обработки всех символов нужно проверить стек. Если он пуст, выражение корректно; если остались открывающие скобки, выражение незавершённо. Обратите внимание: одинаковое количество открывающих и закрывающих скобок не спасает от неправильного порядка." | По таблице доводят пример «{[()]}» до конца, получают пустой стек и вывод «правильно». Анализируют «{[(])}», находят несоответствие: «]» пытается закрыть «(». |
3 мин | Учитель записывает псевдокод: "stack = пустой; для каждого символа: если открывающая — добавить; если закрывающая — проверить вершину и извлечь; после цикла проверить пустоту. Вставьте в пропуски два условия, без которых алгоритм будет ошибочным." | Вписывают условия «стек пуст» и «вершина не соответствует закрывающей скобке», сравнивают ответы с партнёром. |
Запись в тетрадях
Алгоритм: 1) создать пустой стек; 2) читать выражение слева направо; 3) открывающую скобку помещать в стек; 4) при закрывающей скобке проверить, что стек не пуст и вершина соответствует этой скобке, затем удалить вершину; 5) после обработки строки выражение правильное тогда и только тогда, когда стек пуст и ошибок не обнаружено.
Завершение этапа: учитель подводит итог: "Мы получили не просто правило, а полный алгоритм с проверкой двух видов ошибок. Сейчас проверим его на разных выражениях и научимся объяснять каждый шаг."
Этап 5. Первичное закрепление в парах (7 мин)
Цель этапа: закрепить алгоритм через ручную трассировку и взаимную проверку.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель распределяет роли: "В каждой паре первый ученик — оператор стека, второй — контролёр. Оператор называет действие, контролёр проверяет запись. Через три минуты поменяйтесь ролями." Раздаёт карточки с выражениями «([]{})», «([)]», «((()))», «}{». | Распределяют роли, получают карточку и лист трассировки. |
4 мин | Учитель напоминает: "Не ограничивайтесь ответом «правильно» или «неправильно». Обязательно укажите символ, на котором возникла ошибка, или покажите, что стек стал пустым. Для выражения «([)]» назовите вершину перед обработкой символа «)»." | Пошагово обрабатывают выражение, фиксируют состояние стека, находят место ошибки. Для «([)]» объясняют: "Вершина — [, а закрывающая скобка ) ей не соответствует". |
2 мин | Учитель организует взаимопроверку: "Обменяйтесь карточками с соседней парой. Проверьте три пункта: порядок, соответствие скобок, итоговое состояние стека. Поставьте две звезды за верную трассировку и одно пожелание, если объяснение можно уточнить." | Проверяют чужую трассировку, отмечают две сильные стороны и одно улучшение, исправляют собственную запись. |
Завершение этапа: учитель подводит итог: "Ручная трассировка показала, что стек позволяет точно установить место ошибки. Теперь перенесём тот же ход рассуждений в программу и проверим его на компьютере."
Этап 6. Практическая работа с ИКТ (9 мин)
Цель этапа: реализовать алгоритм проверки скобочного выражения в программной среде и протестировать его на разных входных данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель выводит на экран заготовку и объясняет: "Создайте пустой список stack и логическую переменную correct. При чтении символа добавляйте открывающую скобку. Для закрывающей сначала проверяйте пустоту списка, затем последний элемент и удаляйте его. Не копируйте код механически: соотносите каждую строку с этапом алгоритма." | Открывают среду программирования, создают список стека и переменную результата, подписывают роли в паре. |
4 мин | Учитель предлагает реализовать соответствия через словарь: "Для закрывающей скобки удобно хранить ожидаемую открывающую: для ) — (, для ] — [, для } — {. Если стек пуст или вершина не совпала, установите correct = False." Учитель консультирует пары с затруднениями. | Пишут программу, запускают её для строк «{[()]}», «([)]», «((()))», «(». Получают ожидаемые результаты и исправляют синтаксические или логические ошибки. |
3 мин | Учитель даёт граничные тесты: "Проверьте пустую строку, строку без скобок, выражение «(()())» и выражение «())». Обсудите, какой результат должен быть для каждого теста и почему." | Вводят тесты, сравнивают фактический вывод с прогнозом, фиксируют результаты в тетради. Формулируют: "Пустая строка и строка без скобок не содержат ошибок, поэтому стек остаётся пустым". |
Эталон решения
Псевдокод: stack = []; correct = True. Для каждого символа строки: если символ — открывающая скобка, добавить его в стек. Иначе, если символ — закрывающая скобка, проверить условие «стек пуст или stack[-1] не соответствует символу». При выполнении условия установить correct = False и завершить обработку. Иначе удалить вершину. После цикла вывести «правильное», если correct истинно и стек пуст, иначе вывести «неправильное».
Завершение этапа: учитель подводит итог: "Программа повторила нашу ручную модель: вершина стека хранит последнюю незакрытую скобку. Мы протестировали обычные и граничные случаи. Осталось проверить, что каждый из вас может самостоятельно объяснить и применить алгоритм."
Этап 7. Самостоятельная работа с самопроверкой (5 мин)
Цель этапа: индивидуально проверить освоение алгоритма и выявить затруднения.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель раздаёт индивидуальные задания: определить результат для «{[()]}», «{[(])}», «((())», «][» и кратко указать причину первого ошибочного результата. Инструкция: "Работайте без обсуждения. Для одного выражения обязательно приведите состояние стека после каждого символа." | Индивидуально определяют корректность четырёх выражений, записывают место ошибки и одну трассировку. |
2 мин | Учитель показывает эталон на экране и говорит: "Сверьте не только итог, но и объяснение. Если ошибка в одном шаге, исправьте её другим цветом и подпишите причину." | Проверяют ответы, выполняют коррекцию. Ожидаемые результаты: «{[()]}» — правильно; «{[(])}» — ошибка на «]»; «((())» — осталась «(»; «][» — ошибка на первом символе. |
Завершение этапа: учитель подводит итог: "Самостоятельная проверка показала, что главный критерий — не количество скобок, а соответствие вершины стека очередной закрывающей скобке и пустота стека в конце."
Этап 8. Рефлексия и домашнее задание (2 мин)
Цель этапа: осознать результат обучения, зафиксировать затруднения и принять домашнее задание.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель раздаёт карточки самооценки и предлагает закончить фразы: "Сегодня я понял…", "Теперь я умею…", "Мне нужно ещё потренироваться…". Затем спрашивает: "Какой тест обязательно должен быть в программе, чтобы обнаружить незакрытую скобку?" | Заполняют карточку, отвечают: "Нужно проверить выражение, в котором после чтения остаётся непустой стек, например «(()»". |
1 мин | Учитель объявляет домашнее задание: "Выполните базовую часть обязательно, среднюю — для углубления, продвинутую — по желанию. В каждой программе добавьте не менее четырёх тестов и подпишите ожидаемый результат." | Записывают домашнее задание, задают уточняющие вопросы, сдают карточки самооценки. |
Завершение этапа: учитель подводит итог: "Сегодня вы открыли алгоритм, который используется далеко за пределами учебной задачи. На следующем уроке мы расширим его и обсудим, как стек применяется при вычислении выражений и проверке вложенных конструкций."
Критерии оценивания практической работы
- «5» — программа правильно обрабатывает все основные и граничные тесты, различает три типа скобок, корректно выявляет преждевременную закрывающую скобку и незакрытую открывающую скобку; ученик может объяснить роль стека.
- «4» — алгоритм в целом верен, корректно обрабатывает основные выражения, но допущена одна неточность в граничном тесте или объяснении; трассировка содержит не более одной исправленной ошибки.
- «3» — ученик понимает назначение стека и верно анализирует часть выражений, но программа или трассировка не обрабатывает один из обязательных видов ошибок.
- «2» — не сформировано понимание принципа LIFO либо программа не позволяет определить корректность выражения даже после подсказки.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что именно хранится в стеке при чтении скобочного выражения? | Проверка понимания назначения структуры данных. |
Почему выражение «([)]» является неправильным, хотя число открывающих и закрывающих скобок совпадает? | Выявление понимания порядка и соответствия скобок. |
Какие два условия нужно проверить при встрече закрывающей скобки? | Диагностика освоения ключевых условий алгоритма. |
Какой тест вы добавили бы в программу для проверки незакрытой скобки? | Оценка умения проектировать граничные тесты. |
Завершающее слово учителя
"Сегодня мы увидели, что стек превращает проверку скобок из интуитивного рассуждения в точный алгоритм. Самая частая ошибка — проверить только количество скобок и забыть о порядке их закрытия. Запомните: закрывающая скобка должна соответствовать вершине стека, а после обработки всего выражения стек обязан быть пуст. Дома закрепите алгоритм в программе и обязательно используйте граничные тесты. На следующем уроке мы рассмотрим другие задачи, в которых принцип LIFO помогает обрабатывать вложенные конструкции."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Написать программу проверки правильности выражений с круглыми, квадратными и фигурными скобками. Проверить не менее 6 строк, включая «()», «{[()]}», «([)]», «((())», «][» и пустую строку. Для каждого теста записать ожидаемый результат. | Закрепляет базовый алгоритм и проверку двух типов ошибок. При проверке смотреть на соответствие вершины стека и итоговую проверку пустоты стека. |
Средний (повышающий) | Составить трассировочные таблицы для четырёх выражений: «{([])}», «{[}]», «(()[])» и «())». Затем доработать программу так, чтобы она выводила позицию первого ошибочного символа. | Развивает пошаговый анализ, работу с индексом и умение объяснять место возникновения ошибки. |
Продвинутый (дополнительный) | Разработать программу, которая при корректном выражении выводит его подтверждение, а при ошибке сообщает тип: «лишняя закрывающая скобка», «несоответствие типов» или «незакрытая открывающая скобка». Подготовить не менее 8 собственных тестов. | Формирует навык проектирования расширенного алгоритма и классификации ошибок; при проверке смотреть на полноту тестов и обоснованность сообщений. |
Контрольные вопросы перед выходом из класса: «Какой принцип лежит в основе стека? Что происходит со стеком при встрече открывающей скобки? Как обнаружить преждевременную закрывающую скобку? Что означает непустой стек после завершения обработки строки?» Ответы для самопроверки: «LIFO»; «она помещается в стек»; «стек пуст или его вершина не соответствует закрывающей скобке»; «осталась незакрытая открывающая скобка».