Информатика -продвинутый курс




МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ - часть 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('введи арифметическое выражение: ');




Содержание  Назад  Вперед