Стеки. Часть 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

Для начала введем класс скобки. Вообще, без ООП в данной задаче вполне можно обойтись, но все, же так будет удобнее и красивее. Назовем класс TBracket.

У него будет два доступных только для чтения свойства типа char: Open и Close. Соответственно открывающаяся и закрывающаяся скобка. Тип открывающей скобки передается как параметр конструктору, в котором задается соответствующая закрывающаяся скобка.

  1. TBracket = class
  2. private
  3.   FOpen: char;
  4.   FClose: char;
  5. public
  6.   constructor Create( setOpen: char );
  7.  
  8.   property Open: char read FOpen;   // Открывающаяся скобка
  9.   property Close: char read FClose; // Закрывающаяся скобка
  10. end;
  11.  
  12. //...
  13.  
  14. constructor TBracket.Create( setOpen: char );
  15. begin
  16.   FOpen := setOpen;
  17.   // Если setOpen не является открывающейся скобкой, получаем ошибку
  18.   if not (setOpen in ['{','[','(']) then
  19.     raise Exception.Create('Неизвестный вид скобок');
  20.  
  21.   // Находим парную скобку
  22.   case setOpen of
  23.     '(': FClose := ')';
  24.     '[': FClose := ']';
  25.     '{': FClose := '}';
  26.   end;
  27. end;

Интерфейс приложения будет состоять из трех компонент:

  • BracketEdit: TEdit– поле, куда вводится выражение для проверки
  • CheckButton: TButton – кнопка, при нажатии на которую, проверка собственно и выполняется
  • ErrorList: TListBox – поле, куда выводятся сообщения об ошибках.

В качестве поля формы нужно сделать объект Stack типа  TStStack, класса стека разработанного нами ранее.

В обработчике события OnCreate формы нужно создать стек, а в OnDestroy уничтожить.

  1. procedure TMainForm.FormCreate(Sender: TObject);
  2. begin
  3.   Stack := TStStack.Create;
  4. end;
  5.  
  6. procedure TMainForm.FormDestroy(Sender: TObject);
  7. begin
  8.   Stack.Free;
  9. end;

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

  1. function TMainForm.CheckBracket( CheckStr: string ): TStringList;
  2. var
  3.   i: integer;
  4.   ResultList: TStringList;
  5. begin
  6.   // Очищаем стек
  7.   Stack.Clear;
  8.   // Создаем список для ошибок
  9.   ResultList := TStringList.Create;
  10.  
  11.   // Посимвольно пробегаем выражение
  12.   for i := 1 to Length( CheckStr ) do
  13.     begin
  14.        // Если символ не является скобкой, то дальнейший код не выполняется
  15.        if not ( CheckStr[i] in ['{','[','(','}',']',')'] ) then
  16.          Continue;
  17.        
  18.        // Если скобка открывающаяся
  19.        if CheckStr[i] in ['{','[','('] then
  20.          Stack.Push( TBracket.Create( CheckStr[i] ) ) // Кладем ее в стек
  21.        else
  22.          if Stack.Count > 0 then // Если стек не пуст выполняем проверку
  23.            if TBracket(Stack.Peek).Close <> CheckStr[i] then
  24.              ResultList.Add( 'Неcовместимый тип открывающей и закрывающей' +
  25.                'скобки ' + TBracket(Stack.Peek).Open + ' и ' + CheckStr[i]  )
  26.            else Stack.Pop.Free; // Выталкиваем скобку
  27.          else // Если стек пуст, получаем ошибку
  28.            ResultList.Add( 'Лишная закрывающая скобка: ' + CheckStr[i] );
  29.  
  30.     end;
  31.    
  32.   // Если после проверки остались открытые скобки,получаем ошибку
  33.   if Stack.Count > 0 then
  34.     ResultList.Add( 'Не все скобки закрыты!' );
  35.  
  36.   Result := ResultList;
  37. end;

Так же нужная функция ShowError, она принимает список ошибок и выводит их на экран.

  1. procedure TMainForm.ShowError( ErrList: TStringList );
  2. var
  3.   i: integer;
  4. begin
  5.   ErrorList.Items.Clear;
  6.  
  7.   if ErrList.Count > 0 then
  8.     for i := 0 to ErrList.Count - 1 do
  9.       ErrorList.Items.Add( ErrList[i] )
  10.   else
  11.     ErrorList.Items.Add( 'Ошибок не обнаружено' );
  12. end;

И наконец, теперь в обработчике события OnClick для кнопки CheckButton можно прописать следующее:

  1. ShowError(  CheckBracket( BracketEdit.Text )  );

Теперь мы получили полностью работоспособное приложение.

Скачать исходные коды и exe файл можно здесь.

delphi, структуры данных, алгоритмы
3 09 июля 2010 | Стеки

Комментарии (0)

Добавить комментарий

  • Допустимые html-теги:
    <b> </b> - жирный шрифт
    <em> </em> - наклонный
    <s> </s> - зачеркнутый
    <pre> </pre> - сохранение отступов (печать кода)
    [?]
Введите текст с картинки