Задача в паскале: реализовать рекурсивный алгоритм правильности расстановки скобок

Интересная задачка. Я бы сделал без рекурсии. Просто бежать по строке слева направо.

Встретил открывающую скобку — пишу ее в стек или массив.
Встретил закрывающую скобку — смотрю, что последним попало в мой стек или массив.

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

строка :=
пустая строка
или
символ + строка
или
строка + символ
или
(строка) + строка
или
[строка] + строка
или
{строка} + строка
или
<строка> + строка

Простое и быстрое решение (берегите мозг! Там спагетти-код): http://rextester.com/HWEMK33437

.

Быстрое - потому что, к сожалению, для таких задач в паскале нет ничего быстрее прямого перебора... Даже если диалект включает in, этот оператор фактически приводит к копированию памяти... и при большом количестве вызовов, оно все безобразно тормозит. А операция взятия элемента по индексу, к копированию не приводит - хотя в данном конечно эт конкретном случае, это не работает: мы все равно теряем на передаче строки (создается ее локальная копия, т. к. вносим изменения. Можно обойти это просто передавая вместе с j доп. параметром, и выводя посимвольно - код будет еще ужаснее выглядеть :D ).

В общем, если будете что-то писать помимо учебы, в реальных проектах никогда так не делайте...

const b: array [boolean] of string=('НЕ правильно','правильно');
var p: integer;// номер символа в строке
s: string;

function fn(x: string; y: string): boolean;
var c: char; f: boolean;
begin
f:=y='';
repeat
inc(p);
c:=x[p];

if c=y then// закрытие
begin
fn:=true;
exit;
end;

if c in ['(','<','[','{'] then // открытие
begin
case c of
'(': f:=fn(x,')');
'<': f:=fn(x,'>');
'[': f:=fn(x,']');
'{': f:=fn(x,'}');
end;
end;

if c in [')','>',']','}'] then // нежданчик
begin
fn:=false;
exit;
end;
until p>=(length(x));
fn:=f and (y='');
end;

begin
s:='ab{cd()}[,,,,]';p:=0;writeln('В ',s,' скобки расставлены ',b[fn(s,'')]);
s:='ab{cd()}[,,<,]';p:=0;writeln('В ',s,' скобки расставлены ',b[fn(s,'')]);
s:='([)]';p:=0;writeln('В ',s,' скобки расставлены ',b[fn(s,'')]);
s:='(((()..';p:=0;writeln('В ',s,' скобки расставлены ',b[fn(s,'')]);
end.

/////////
В ab{cd()}[,,,,] скобки расставлены правильно
В ab{cd()}[,,<,] скобки расставлены НЕ правильно
В ([)] скобки расставлены НЕ правильно
В (((().. скобки расставлены НЕ правильно

Интересная задачка. Я бы сделал без рекурсии. Просто бежать по строке слева направо.

Встретил открывающую скобку — пишу ее в стек или массив.
Встретил закрывающую скобку — смотрю, что последним попало в мой стек или массив.

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

Это задачу можно решить с помощью ветвлений