Иногда возникает проблема проверки корректности скобочной структуры. Рассмотрим подробно эту проблему.

Пусть в строке хранится выражение, содержащее скобки: ‘(’ и ’)’. Для понятности определения корректности скобочной структуры рассмотрим примеры:

( ( ) ) – скобочная структура корректна
( ( ) – скобочная структура не корректна
( ) ) – скобочная структура не корректна

Из рассмотренных примеров можно выдвинуть гипотезу.

Гипотеза: «Скобочная структура корректна когда количество открывающих скобок ‘(’ равно количеству закрывающих ‘)’»

Но рассмотрим контрпример: ) ( - скобочная структура не корректна. Но по нашей гипотезе данная скобочная структура будет считаться корректной. В данном случае количество открывающих скобок равно количеству закрывающих, но закрывающая скобка идет раньше, чем открывающая. Из этих утверждений сформулируем правило: «Скобочная структура корректна тогда и только тогда, когда количество открывающих скобок ‘(’ равно количеству закрывающих ‘)’ и нет такого момента времени (при проверке скобок слева направо по одной) когда количество закрывающих скобок больше чем открывающих».

Заведем переменную Rang – числовая характеристика корректности скобочной структуры. В процессе проверки если встречаем ‘(’ то увеличиваем rang на 1, если ’)’, то уменьшаем rang на 1.
Тогда правило переформулируется так: «Если в процессе проверки rang не был меньше 0, а в конце проверки rang = 0, то такая скобочная структура корректна»

Алгоритм проверки:

1. Ввод данных
2. Rang:=0;
3. i:=1;
4. Если i’ый элемент строки ‘(’, то увеличиваем Rand на 1
5. Если i’ый элемент строки ‘)’, то уменьшаем Rand на 1
6. увеличить i на 1
7. Если i больше чем длина строки или Rang < 0 то перейти к п.9
8. Перейти к п. 4
9. Если Rang = 0 то вывод (‘Структура корректна’) иначе вывод(‘Структура не корректна’)
10. Конец

Вот как это будет выглядеть:

var s:string;
    i,rang:integer;
begin
     writeln('Введите строку');
     readln(s);
     rang:=0;
     for i:= 1 to length(s)do
     begin
          if s[i]='('then inc(rang);
          if s[i]=')'then dec(rang);
          if rang<0 then break;
     end;
     if rang=0 then writeln('Скобочная структура верна') 
               else writeln('Скобочная структура не верна');
     readln;
end.

Пусть у нас есть строка содержащая 3 вида скобок:

‘(‘, ‘)’, ’[’ , ’]’, ’{’, ’}’

Использование 3х типов скобок не позволяют создать правильный алгоритм анализа скобочной структуры с использованием Rang. Воспользуемся стеком.

Алгоритм.

1. Двигаемся вдоль скобочной структуры.
2. Если встретилась открывающая скобка любого вида, то помещаем её в стек.
3. Если встретилась закрывающая скобка, то извлекаем из стека верхнюю скобку и сравниваем их тип (Например ‘{’ и ’}’ – одного типа)
   Если скобки непарные, то скобочная структура неверна.
4. Если в процессе анализа была попытка извлечения из пустого стека, то скобочная структура неверна.
5. Если после завершения проверки стек не пуст, то скобочная структура неверна.

Для различного типа скобок можно сформулировать ещё одно важное, но очевидное правило:
Скобочные пары двух или более разных типов не могут иметь пересекающуюся структуру.

Вот пример, демонстрирующий правильность этого утверждения: [{]} - тут нём две скобочные пары пересекаются, хотя и формируют (независимо друг от друга) верные пары.
При дальнейшем рассмотрении этого правила можно заметить такое следствие: внутри любой пары скобок одного типа может быть только лишь чётное количество скобок другого типа, либо их может вобще не быть. Если это число не чётное, то содержимое этой пары скобок сформировано неправильно.

12345678
([{})])

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

Еще один вариант рещения данной задачи:

Пока нам встречаеся последовательность из открывающей и закрывающей скобки одного вида, мы их удаляем. В конце:
а) если удалены все скобочные пары (т.е. длина строки в конце равна 0), то скобочное выражене коректно.
б) не все скобки удалены - значит, скобочное выражение неверно.

Пример:

({[()]})[{}]

Сначала алгоритм находит ():

({[]})[{}]

Потом {}:

({[]})[]

Потом 2 раза []:

({})[] и ({})

Опять {}:

()

И, наконец, (): пустая строка
Скобочное выражение было верным.

Function IsCorrect(Expr : String) : Boolean;
Var R : Boolean;
Begin
 Repeat
  R:=False;
  If (Pos('()', Expr) > 0) Then
   Begin
    Delete(Expr, Pos('()', Expr), 2);
    R:=True;
   End;
  If (Pos('{}', Expr) > 0) Then
   Begin
    Delete(Expr, Pos('{}', Expr), 2);
    R:=True;
   End;
  If (Pos('[]', Expr) > 0) Then
   Begin
    Delete(Expr, Pos('[]', Expr), 2);
    R:=True;
   End;
 Until R = False; 
 IsCorrect:=Length(Expr) = 0;
End;