Форум на Исходниках.RU

Анализ скобочной структуры

tserega — Mon, 01 Mar 2004 19:28:54 +0000

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

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;

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

Пример:
({[()]})[{}]
Сначала алгоритм находит () : ({[]})[{}]
Потом {}: ({[]})[]
Потом 2 раза []: ({})[] и ({})
Опять {}: ()
И, наконец, (): пустая строка
Скобочное выражение было верным.

Анализ скобочной структуры

Some1 — Sat, 03 Jan 2004 12:12:58 +0000

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

Анализ скобочной структуры

@Hgpeu — Sat, 03 Jan 2004 03:59:44 +0000

@Hgpeu: Анализ скобочной структуры.

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

Скобки одного вида.

Пусть в строке хранится выражение, содержащее скобки: ‘(’ и ’)’. Для понятности определения корректности скобочной структуры рассмотрим примеры:
( ( ) ) – скобочная структура корректна
( ( ) – скобочная структура не корректна
( ) ) – скобочная структура не корректна
Из рассмотренных примеров можно выдвинуть гипотезу.
Гипотеза: «Скобочная структура корректна когда количество открывающих скобок ‘(’ равно количеству закрывающих ‘)’»
Но рассмотрим контр пример: ) ( - скобочная структура не корректна.
Но по нашей гипотезе данная скобочная структура будет считаться корректной.
В данном случае количество открывающих скобок равно количеству закрывающих, но закрывающая скобка идет раньше, чем открывающая. Из этих утверждений сформулируем правило: «Скобочная структура корректна тогда и только тогда, когда количество открывающих скобок ‘(’ равно количеству закрывающих ‘)’ и нет такого момента времени (при проверке скобок слева направо по одной) когда количество закрывающих скобок больше чем открывающих».
Заведем переменную 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. Если после завершения проверки стек не пуст, то скобочная структура неверна.