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

[tarasman11]

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

[Mandrivnyk]

И в чем проблема?
Заводишь два счетчика и считаешь посимвольно.
Встречаешь открывающую скобку -- увеличиваешь счетчик, закрывающую уменьшаешь.
В любой точке строки счетчик не может быть отрицательным.
Еще надо условие на то, чтобы скобки не перекрывали друг друга -- вот так, к примеру:
( ( [ ) ] ) -- это неправильно.

Ну, и в конце строки счетчики должны быть равны нулю.

[ViktorR]

Эту задачу можно решить для любого вида скобок следующим образом:
Задаешь код скобок:
{ - 3 (плюс 3)
[ - 2 (плюс 2)
( - 1 (плюс 1)
) - -1 (минус 1)
] - -2 (минус 2)
} - -3 (минус 3)
Формируешь стек, в который вкладываешь всякую открывающуюся скобку (>0). Если скобка закрывающаяся (<0), то проверяешь стек. Если пуст, то ошибка иначе извлекаешь из стека число.
Складываешь извлеченное число с имеющимся. Если ноль, то все Ок иначе ошибка.
Это стандартный алгоритм.

Как то так ...

[Serge_Bliznykov]

VktorR, сдаётся мне, что алгоритм описанный в вашем случае НЕ РАБОТОСПОСОБЕН (по крайней мере напрямую, так, как Вы его описали!)

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

[Utkin]

Стек здесь излишняя бюрократия. Входящий поток символов уже можно рассматривать как стек, просто пропуская любые символы не являющиеся скобками. А если стек уже по сути есть, то зачем заводить еще один? Нафига два цикла когда можно воспользоваться одним?
Общую схему действий уже расписал Mandrivnyk - рабочая, я использовал подобную (только вместо квадратных скобок у меня были еще угловые < и >). Писал на c#, но алгоритм по сути тот же.

[Rififi]

ViktorR

Задаешь код скобок:
{ - 3 (плюс 3)
[ - 2 (плюс 2)
( - 1 (плюс 1)
) - -1 (минус 1)
] - -2 (минус 2)
} - -3 (минус 3)

{)))

:LOL:

[Serge_Bliznykov]

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

А если стек уже по сути есть, то зачем заводить еще один? Нафига два цикла когда можно воспользоваться одним?

Да нету у Вас стека! А то, что Вы предлагаете - и есть организация стека с помощью строки (по сути строка - это массив символов, а стек легко может быть смоделирован с помощью массива и индекса(позиции) в этом массиве).


впрочем, по сути я с вами согласен. ещу одна дополнительная строчка быстро и удобно смоделирует стек (вот примерный набросок решения):

isError := false;
for i:=1 to Length(s) do
  if s[i] in ['[','(','{'] then Stek := Stek + s[i]
  else 
    if s[i] in [']',')','}'] then 
       if Length(Stek)=0 then 
            begin WriteLn('Ошибка в позиции ',i,' закрывающая скобка без открывающей'); isError :=  true; Break; 
            end
       else begin
          if Stek[Length(Stek)]<>s[i] then 
            begin WriteLn('Ошибка в позиции ',i,
                    ' закрывающая скобка не того типа, что была открывающая - ожидалась скобка ',Stek[Length(Stek)]); 
                isError :=  true; 
                Break; 
            end
          else {вроде всё в порядке - выкидываем последний символ из стека}
            Delete(Stek, Length(Stek), 1);
       end;
 
if (not isError) and (Length(Stek)=0) then
    WriteLn('Строка является корректным скобочным выражением!');
if (not isError) and (Length(Stek)>0) then
    WriteLn('Ошибка, не закрыты открывающие скобки!');

[eoln]

Небольшая поправка по строчке

if Stek[Length(Stek)]<>s[i]

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

if ((Stek[Length(Stek)]='(')and(s[i]<>')')) or
   ((Stek[Length(Stek)]='[')and(s[i]<>']')) or
   ((Stek[Length(Stek)]='{')and(s[i]<>'}')) then ...

Или же в стек добавлять обратные скобки, т.е. вместо

if s[i] in ['[','(','{'] then Stek := Stek + s[i] else

писать

if s[i] ='[' then Stek := Stek + ']' else
  if s[i] ='(' then Stek := Stek + ')' else
  if s[i] ='{' then Stek := Stek + '}'
  else

[Serge_Bliznykov]

eoln, я понял, о чём! Конечно же, когда мы встретили ЗАКРЫВАЮЩУЮ скобку, она НИКАК не будет равна открывающей!

это ошибка с моей стороны, эту мелочь надо учесть и исправить!


могу предложить такой вариант обхода:

const
  OtrkSkb = '[({';
  ZakrSkb = '])}'; {внимание! Порядок должен быть одинаковым!}
var
  i: integer;
  s, Stek: string;
  isError: boolean;
begin
  s :=
    '( vot { ([ 1+2 ] * 2) } )';

  isError := false;
  Stek := '';
  for i := 1 to Length(s) do
    if Pos(s[i], OtrkSkb) > 0 then Stek := Stek + s[i]
    else
      if Pos(s[i], ZakrSkb) > 0 then
        if Length(Stek) = 0 then
        begin WriteLn('Ошибка в позиции ', i, ' закрывающая скобка без открывающей'); isError := true; Break;
        end
        else begin
          if Pos(Stek[Length(Stek)], OtrkSkb) <> Pos(s[i], ZakrSkb) then
          begin WriteLn('Ошибка в позиции ', i,
              ' закрывающая скобка не того типа, что была открывающая - ожидалась скобка ', Stek[Length(Stek)]);
            isError := true;
            Break;
          end
          else {вроде всё в порядке - выкидываем последний символ из стека}
            Delete(Stek, Length(Stek), 1);
        end;

  if (not isError) and (Length(Stek) = 0) then
    WriteLn('Строка является корректным скобочным выражением!');
  if (not isError) and (Length(Stek) > 0) then
    WriteLn('Ошибка, не закрыты открывающие скобки!');

  readln
end.

[tarasman11]

напишите полностью правильный код пож