Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Дерево как последовательность ветвей

Анализ алгоритма вычисления.

Дано выражение в текстовом файле. Вычислить значение выражения.

Дерево – естественная форма представления выражений, но неэффективно по расходу памяти. Если алгоритм сводится к последовательной обработке компонент некоторой последовательности в естественном порядке, не нужно держать в памяти всю последовательность. В алгоритме вычисления в каждый момент времени используются сведения лишь об одной ветке дерева (ссылка на которую хранится в стеке).

 

function NewNode(c:char):pNode;

var NewPt:pNode;

begin

new(NewPt);

NewPt^.info:=c;

NewPt^.left:=nil;

NewPt^.right:=nil;

NewNode:=NewPt;

end;

 

type

tInfo=record

case этоInteger:boolean of

true (IntInfo:integer);

false (CharInfo:char);

end;

end;

 

function ExpVal(var exp:text;VarVal: tVarVal):integer; {tVarVal» tVariable)}

var stack:tStack; {tStack of tInfo}

begin

create(stack); {Стек символов}

ReadChar(exp,f);

ReadChar(exp,x);

push(stack,f);

push(stack,x);

while not eof(exp) do

begin

{Пока не нашли атом, читай символы и складывай в стек}

pop(stack,x);

pop(stack,f); {/*+x1y2}

ReadChar(exp,c);

while not Atom(f,x,y) do

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadChar(exp,c);

end;

push(stack,AtomVal(f,x,y));

end;

pop(stack,x);

ExpVal:=x.IntInfo;

end;

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

 

Задача синтаксического анализа.

На первый взгляд эта задача кажется совсем не похожей на задачу о вычислении. В реальности это практически та же задача.

Дана произвольная символьная последовательность. Выяснить, является ли она правильно построенным выражением.

/*+x1y2 – true

-*+x1y23 – false

Шаблоном текста c1,…,cn назовём текст ­­­c1|,…,cn|, где

 
 


‘t’, ci – терм

ci|= ‘f’, ci – знак операции

‘Æ’, ci – чужой (посторонний) символ.

 

Шаблоном атома назовём строку c1,c2,c3. Это либо строка f,t,t, где c1=f, c2=t, c3=t, либо хотя бы один их них равен Æ.

Формальным вычислением назовём переход от шаблона атома c1,c2,c3 к символу ‘t’ в случае ftt, либо к символу ‘Æ’ во втором случае. (?)

Последовательность есть выражение, если его можно преобразовать формальным вычислением к символу ‘t’.

procedure ReadMask(var exp:text;var m:char);

{Определение шаблонов атомов}

begin

if eof(exp) then m:=’Æ’

else

begin

read(exp,c);

if c in [‘+’, ’-‘, ’/’, ’*’] then m:=’f’

else if c in [‘a’..’z’]+[‘0’..’9’] then m:=’t’

else m:=’Æ’;

end;

end;

 

function CorrectExp(var exp:text):boolean;

begin

reset(exp);

create(stack);

ReadMask(exp,f);

push(stack,f);

b:=(f<>’Æ’) and (f =’t’) and not eof(exp);

ReadMask(exp,x);

push(stack,x);

b:=b and (x<>’Æ’);

while b and not eof(exp) do

begin

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

while not AtomMask(f,x,y) do{проверяем на атом}

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

end;

result:=AtomMaskVal(f,x,y);{Вычисляем шаблон}

push(stack,result);

b:=result<>0;

end;

CorrectExp:=(x=’t’) and empty(stack);

end;

 

<== предыдущая лекция | следующая лекция ==>
Представление записи | Графы-выражения
Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 409; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.