Информатика -продвинутый курс
МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ - часть 2
Для решения подобных задач используют стековую память (называемую просто «стек»). Стек представляет последовательность данных и имеет лишь одну границу для добавления и удаления элементов. В нашем случае в стек помещаются и удаляются скобки.
Первым необходимым условием правильности расстановок скобок является совпадение количества левых и правых скобок. Такой контроль легко осуществить введя счетчик top, который при просмотре выражения и обнаружении левой скобки (допустим, что имеем только круглые скобки '(' ) увеличивается на +1. Если на очередном месте встретилась правая скобка, то значение счетчика уменьшается на 1. Тогда правильность расстановки определяется по итоговому значению top.
Программа 36
program skobkal; (*проверка скобок по количеству*)
var top, i, n: integer; slovo: string[100]; skob: string[100];
begin
write('введи арифметическое выражение: ');
readln(slovo); n:length(slovo);
top:=0; skob:=''; i:=l;
while (i<=n) do begin
if slovo[i]=')' then begin top:=top+1; skob:=skob+slovo[i] end;
if slovo[i]=')' then begin
top:=top-l; skob:=skob+slovo[i] end;
i:=i+l
end;
writeln(skob) ;
if top=0 then write('выражение
правильное') i else write('выражение
неправильное');
readln .
end.
Строковая переменная skob предназначена "для визуализации всех имеющихся скобок в выражении.
В случае, когда в выражении используются фигурные, квадратные и круглые скобки, задача усложняется тем, что необходим еще контроль соответствия левых и правых скобок. В этой связи удобно использовать стек, в котором помещаются очередные левые скобки. При обнаружении правой скобки из вершины стека извлекается левая скобка, помещенная последней, и проводится их идентификация. Полный текст программы представлен ниже.
Программа 37
program skobka2; (*проверка расстановок скобок*) var top, i, n: integer;
slovo: string[100];
store: array [1. . 100] of char; -x: char.; sicob: string[100];
p: boolean;
begin
write('введи арифметическое выражение: ');
