Delphi::Стеки. Часть 2. Расстановка скобок

В первой части цикла статей был реализован класс стека. Сейчас мы рассмотрим применение стека для решения одной, в общем-то, классической задачи по программированию.

Задача

Необходимо проверить правильность расстановки скобок “(), {}, []” в выражении. То есть проверить, все ли скобки закрыты, соответствует ли закрывающаяся скобка открывающейся, нет ли лишних закрывающихся скобок и тд.

К примеру, такое выражение 2 * ( 3 – [ x+ 3 ] / 15 ) – { 2 + 3 } * 5 проверку пройдет, а 2 * ( 3 – [ x+ 3 ) / 15 ] – { 2 + 3 } * 5 уже нет.

Алгоритм решения

Рассмотрим сначала общий словесный алгоритм решения. Полагаю, можно обойтись без псевдокодов и блок-схем.

• Проходим посимвольно все выражение
• Проверяем, является ли текущий символ скобкой
  • Если эта скобка открывающаяся, тогда кладем ее в стек
  • Если же нет, тогда, проверяем, есть ли в стеке элементы
    • Если да, тогда находим закрывающуюся скобку, для той, которая лежит на вершине стека. Проверяем ее с текущей скобкой, если они не равны, то ошибка. Если равны, то выталкиваем скобку из стека.
    • Если же стек пуст, тогда получаем, что нашли закрывающуюся скобку, хотя позади нет ни одной открытой, следовательно, ошибка
• После того, как прошли выражение, проверяем, остались ли в стеке скобки, если остались, следовательно, не все скобки закрыты

В общем, смысл в том, что все открывающиеся скобки мы скидываем в стек, и как только встретится закрывающиеся, проверяем является ли она парой, той, которая на вершине стека.

Для лучшего понимания это можно рассмотреть на примере.

Возьмем выражение 2 * ( 3 – [ x + 3 ] / 15 }– { 2 + 3 }* 5].

Находим первую открывающееся скобку, это будет «(», кладем ее в стек, идем далее. Доходим до скобки «[», тоже кладем ее в стек. К тому времени, как мы дойдем до скобки «]», стек уже будет «(, [», проверяем вершину стека: «[» и скобку «]», как видно они пара. Следовательно скобку [ выталкиваем из стека. Идем далее до скобки }. На это время в стеке у нас осталась только «(», очевидно, что парой для } она не является, получаем ошибку. На этом, в общем-то программу можно прервать, то лучше дойти до конца и получить полный список ошибок. Скобку { кладем в стек, после проверки со следующей }, так как они пара, то { можно вытолкнуть. В стеке опять осталась только (. Дошли до последней скобки ]. Снова получаем ошибку, так как ( и ], собственно не пара. И так же, поскольку после обхода, у нас в стеке все еще осталась скобка (, то получаем еще одну ошибку, что не все скобки закрыты...

Delphi::Стеки. Часть 1

В современной литературе, посвященной обучению программированию, обсуждение вопросов, касающихся структур данных, стало встречаться крайне редко. И часто случается, что человек, прочитавший не одну книгу по какой-нибудь Delphi, довольно отдаленно представляет себе, что такое стеки и очереди, односвязные или двусвязные списки и т.п.

В этом цикле статей мы рассмотрим стеки. Сначала дадим общее определение, потом попробуем реализовать собственный класс стека. В конце напишем классическое приложение для демонстрации работы стека – проверка правильности расстановки скобок в выражении. Так же немного коснемся класса TStack, уже реализованного в Delphi.

Стек.

Стек – это структура данных, доступ к которым осуществляется лишь с одного конца, называемого вершиной стека. То есть получить элемент можно только, тот, который лежит на вершине стека, а что бы взять следующий, первый нужно вытолкнуть.

Добавление (проталкивание) элемента возможно только на вершину стека, при этом добавляемый элемент сам становиться верхним. Удаление (выталкивание),  так же возможно только с вершины. В общем, доступ в стеке есть лишь к верхнему элементу.

Реализация стека.

Вообще, конечно, самому писать класс стека это изобретение велосипеда. В Delphi уже есть стеки на все случаи жизни, но это полезно в образовательных целях.

Для начала нужно выбрать структуру, на которой будет строиться стек. Как правило, это либо односвязные списки, либо массивы. Поскольку в Delphi есть  динамические массивы, и с ними работать довольно удобно, то их и можно использовать как основу стека... читать дальше