Проверить правильность расстановки круглых и квадратных скобок в выражениях

[ViktorR]

Алгоритм описан в книге:
А. Шень, Программирование. Теоремы и задачи. 2004
Насколько верно/не верно он описан и насколько эффективно использовать этот алгоритм не спорю. Просто приведу свою реализацию:
Program MyProg_01;
{Эта часть из Т.А. Павловская. Программирование на ЯВУ. Паскаль}

Type TNode = ^Node; {описание узла стека}
     Node = Record
        i: Integer;
        p: TNode;
     End;

Function Push(Top: TNode; I: Integer): TNode; {Вложить в стек}
var p: TNode;
begin
   new(p);
   p^.i := I;
   p^.p := Top;
   push:= p;
end;

Function Pop(Top: TNode; var I: Integer): TNode; {Извлечь из стека}
var p: TNode;
begin
   I:= Top^.i;
   Pop:= Top^.p;
   Dispose(Top);
end;

{Тут моя вариация}
Function Bracket2Nomber(ch: Char): Integer; {Нумерация скобок и иных символов}
begin
   case ch of
     '{': Bracket2Nomber := 3;
     '}': Bracket2Nomber := -3;
     '[': Bracket2Nomber := 2;
     ']': Bracket2Nomber := -2;
     '(': Bracket2Nomber := 1;
     ')': Bracket2Nomber := -1;
     else Bracket2Nomber := 0; {иные символы}
   end;
end;

var fh: Text;
    str: String;
    Top: TNode;
   Ok, Err: Boolean;
    i, k, m, n, z: Integer;

BEGIN
 {Файл со строками. Программа рассматривает каждую строку отдельно}
   assign(fh,'c:\MyTst\Test.txt');
   reset(fh);
   k := 0; {номер прочитанной строки}
   While Not Eof(fh) do begin {Пока не конец файлв}
     readln(fh, str); {Читаем строку}
    k := k + 1;
     Top := Nil;       {Указатель на вершину стека обнуляем}
     i := 0;             {Счетчик символов в строке}
     Err := False;    {Ошибка в конфигурации скобок}
     n := Length(str);  {Длинна строки}
     while ((i < n) and (NOT Err)) do begin {не конц строки и нет ошибки в конфигурации скобок}
        i := i + 1; {обработаем следующий символ}
        m := Bracket2Nomber(str[i]); {нумеруем символ}
        If m <> 0 Then {скобка}
           If (m > 0) Then {открывающаяся скобка - в стек}
             Top := Push(Top,m)
           Else begin {закрывающаяся скобка}
             If Top = Nil Then {стек пуст}
                Err := True      {это ошибка}
             Else begin {стек не пуст}
                Top := Pop(Top,z); {читаем из стека}
                Err := (z <> -m);   {проверяем на соответствие.}
{ Тут я предлагал сложить и проверить на ноль}
{If ((z+m) =0) Then Err := false  Else Err := true;}
             end; {else}
           end; {else}
     end; {while - просмотрели все символы строки}
     Ok := (NOT Err) AND (Top = Nil); {Ошибка и состояние стека}
   While Top <> Nil do {На тот случай, когда стек не пуст}
   Top := Pop(Top, z);
     writeln('Line: ', k:4, ' ', Ok);   {Номер просмотренной строки и результат на экран}
   end; {while - просмотрели все строки файла}
END.

Как-то так, ...

[Serge_Bliznykov]

ну да. согласен. это вполне рабочий вариант.
вы, когда описывали алгоритм, забыли упомнуть об одной ВАЖНОЙ детали.
о том, что при закрывающей скобке элемент на вершине стека и текущий должны быть СТРОГО одинаковы по модулю, но с разными знаками:

                Err := (z <> -m);   {проверяем на соответствие.}

согласитесь, а эта строчка весьма важна в данном алгоритме!


p.s. а мой вариант не проще (см. пост #9)?

[ViktorR]

Serge_Bliznykov

вы, когда описывали алгоритм, забыли упомнуть об одной ВАЖНОЙ детали.
о том, что при закрывающей скобке элемент на вершине стека и текущий должны быть СТРОГО одинаковы по модулю, но с разными знаками:

Там было так:

Складываешь извлеченное число с имеющимся. Если ноль, то все Ок иначе ошибка.

Это другая версия той же проверки. В моём варианте кода - в комментарии.

Насколько верно/не верно он описан и насколько эффективно использовать этот алгоритм не спорю.

[Serge_Bliznykov]

Сообщение от ViktorR

Там было так:

угу. теперь, после того, как я увидел программу, беру свои слова насчёт неверного алгоритма назад.
Могу сказать, я был уверен, что в вашем алгоритме числа СУММИРУЮТСЯ.
те. если встретились две открывающиеся фигурные скобки {{ - то в стеке получается число 6 (3+3).
Теперь я вижу, что я неправильно понял алгоритм. Числа, соответствующие открывающимся скобкам, хранятся в стеке в виде ОТДЕЛЬНЫХ значений.


p.s. зато теперь в теме есть ДВА различных варианта решения.