Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-12-21 | 190 |
5.00
из
|
Заказать работу |
|
|
Определим арифметическое выражение (в полноскобочной инфиксной записи) как последовательность символов, являющуюся
1) либо термом, т.е.
a) либо именем константы вида b1… bn.c1… cm, где
(n>0) & (m>0) & " iÎ[1,n](biÎ ['0','9']) & " jÎ[1,m](cjÎ ['0','9'])
b) либо именем переменной вида d1… dk, где
(k>0) & (d1Î ['a','z']) & " iÎ[2,k](diÎ ['0','9']È['a','z'])
2) либо строкой вида (E1)f(E2), где E1,E2 - выражения, а f - один из знаков +,-,*,/
Аналогично определяются выражения в префиксной f(E1)(E2), и постфиксной (E1)(E2)f формах.
если Е - выражение вида (E1)f(E2).
Аналогично определяются деревья выражений в префиксной и постфиксной формах. Ясно, что вид дерева не зависит от синтаксиса/структуры сложного выражения. В чем и заключается их прелесть. Минус – больший расход памяти, по сравнению в линейной, строковой форме.
Как перейти от представления выражения деревом к линейной - инфиксной, префиксной и постфиксной форме? Ответ ищи в разных порядках обхода дерева в "Нелинейные типы данных".
Типом выражения E (и, соответственно, вершины, его содержащей) будем называть cимвол-метку 't', если Е - терм, и символ 'f', если Е - выражение, содержащее знак операции.
Задача вычисления дерева выражения. Найти результат выражения при заданных значениях переменных, если выражение представлено деревом.
Строго говоря, для решения задачи мы должны также зафиксировать семантику выражений - что же они на самом деле обозначают? Ясно, что по умолчанию подразумевается традиционная арифметика вещественных чисел.
|
Для того, чтобы кратко и ясно представить основную идею алгоритма как сведение вычисления сложного выражения к вычислению элементарных выражений или атомов (содержащих, по определению, единственный знак операции), будем предполагать, что значения термов (констант и переменных) уже найдены (как это сделать - см. "Задачи текстовой обработки,3") и сохранены в самом дереве.
type
pNode=^tNode;
tNode= record
Name:string;
Val:integer;
left,right:pNode;
end;
Очевидно, это не очень экономное решение в смысле расхода памяти - для двух термов с одинаковым значением мы сохраняем значение дважды, а остальные (содержащие знаки операций) вершины вообще изначально не имеют значения. Обычно значения термов и промежуточные результаты сохраняют во внешних по отношению к дереву таблицах.
{вычисление элементарного выражения}
function AtomVal(root:pExpr):T;
begin
with root^ do
case Name of
'+': AtomVal:=left^.Val+right^.Val;
'-': AtomVal:=left^.Val-right^.Val;
'*': AtomVal:=left^.Val*right^.Val;
'/': AtomVal:=left^.Val/right^.Val;
{для простоты, опускаем обработку исключения - деления на 0}
end; end;
{выяснение типа вершины}
function NodeType(pt:pNode):char;
begin
with pt^ do
if (right=nil) and (left=nil)
then NodeType='t'
else NodeType='f'
end;
{поиск атома, лежащего ниже данной вершины}
{идея: вычисление $-свойства found:=$ ptÎpNode (pt¹nil & pt^.left¹nil & pt^.right¹nil) }
{см."Вычисление свойств"}
{предусловие: вершина pt содержит знак операции, NodeType(pt)='f'}
procedure FindAtom(var pt:pNode; var stack: pStack);
var found:Boolean;
begin
with pt^ do
begin
found:=false;
while not found do
begin
if NodeType(left) ='f'
then begin push(pt,stack); pt:=left end
else if NodeType(right)='f'
then begin push(pt,stack); pt:=right end
else
{ это терм» NodeType(pt)='f' & NodeType(left) ='t' & NodeType(right)='t'}
found:=true
end;
end;
{предусловие - дерево не вырождено, все термы уже означены}
function ExpVal(root:pExpr):T;
var
stack:pStack;
{вспомогательный стек ссылок pNode на еще не вычисленные знаки операций}
{реализацию см. "Абстрактные линейные типы данных"}
found:Boolean; {есть еще атомы?}
RootType,LeftType,RightType:char; {{'t','f')}
begin
Create(stack);
UpperType:=NodeType1(root);
if UpperType='f' then
push(stack,root);
while not empty(stack) {= есть невычисленные операции} do
|
begin
{следующий поиск начинаем c вершины, ближайшей к вычисленному атому}
pop(stack,pt); FindAtom(pt,stack);
{Вычисли значение атомарного выражения}
pt^.val:= AtomValue(pt);
{Сократи дерево}
destroy(pt^.right); pt^.right:=nil;
destroy(pt^.left); pt^.left:=nil;
end;
{Дерево состоит из одной вершины}
ExpVal:=root^.val;
end;
Замечание. Побочным (и не очень желательным) эффектом простоты нашего алгоритма является уничтожение самого дерева. В реальности, мы можем не уничтожать вычисленные термы, а лишь помечать их как уже вычисленные.
Задача. Синтаксический анализ выражения, представленного деревом. Проверить, является ли произвольное бинарное символьное дерево деревом выражения.
Задача синтаксического анализа очевидно распадается на анализ 1) термов и 2) сложных выражений. В данном случае, анализ термов прост и напрямую сводиться к задаче поиска (см. "Поиск"). Центральная идея: свести задачу анализа сложного выражения к задаче вычисления.
1) Анализ термов.
type tSetOfChar=set of char;
{Поиск позиции "исключения" - первого символа в подстроке s[start,finish], не принадлежащего множеству alphabet }
procedure FindException
(s:string; start,finish:Cardinal; alphabet:tSetOfChar; position:Cardinal; found:boolean);
{идея: проверка свойства found=$ positionÎ [start,end] (s[position] Ï alphabet)}
{см."Вычисление свойств" и "Поиск"}
begin
found:=false; position:=start;
while (position<=finish) and (not found) do
if s[position] in alphabet then inc(position) else found:=true;
end; { function FindException }
{проверка имени константы}
function ConstantName(s:string):boolean;
var
position, {позиция "исключения" - см. procedure FindException }
len:Cardinal; {длина выражения s}
found:boolean; {"исключение" найдено}
begin
len:=Length(s); ConstantName:=false;
FindException(s,1,len,['0'..'9'],position,found);
if (position=1) or (position=len) or (not found)
then {нет обязательной внутренней не-цифры} exit; {завершаем}
if s[position]<>'.'
then {эта не-цифра - не точка} exit; {завершаем}
{есть ли не-цифры после точки?}
FindException(s,position+1,len,['0'..'9'],position,found);
ConstantName:=not found
end;
{проверка имени переменной - еще проще}
function VariableName(s:string):boolean;
var
position, {позиция "исключения" - см. procedure FindException }
len:Cardinal; {длина выражения s}
found:boolean; {"исключение" найдено}
begin
len:=Length(s); VariableName:=false;
if len=0 then exit;
if not (s[1] in ['a'..'z']) then exit;
FindException(s,2,len,['0'..'9']+['a'..'z'],position,found);
VariableName:=not found
end;
2) Анализ (сложных) выражений.
Определим понятие расширенного (или просто р-) выражения как строки вида (E1)F(E2), где E1,E2 - произвольные, в том числе пустые строки, а F - произвольная непустая строка. Мотивация - любому невырожденному дереву однозначно сопоставляется некоторое р-выражение.
|
Расширим также понятие типа р-выражения за счет добавления "неопределенного" значения 'Æ': если р-выражение не имеет типа 'f' или 't', то оно имеет тип 'Æ'. Формальным вычислением р-выражения назовем операцию Reduce (сократить, англ):
ì терм 'x', если Тип(E1)=Тип(E2)='t' и Тип(F)='f'
Reduce((E1)F(E2))= í
î 'Æ', в противном случае
(смысл прост - результатом вычисления правильного выражения является терм, а результат вычисления неправильного выражения не определен)
Идея алгоритма: Выражение правильно» тип результата формального вычисления = терм.
{расширенный тип вершины}
function ExtentedNodeType(pt:pNode):char;
var len:Cardinal; {длина строки}
begin
{теперь не уверены, что "листья" дерева - это термы!}
ExtendedNodeType:='Æ';
if pt=nil { тип пустого слова неопределен}
then exit; {= завершить определение значения функции }
with pt^ do
begin
len:=Length(name);
if len=0 then exit;
if (Len=1) and (name[1] in ['+','-','*','/']) and (left<>nil) and (right<>nil)
then begin ExtendedNodeType:='f'; exit end;
if (left=nil) and (right=nil) and
(ConstantName(pt^.name) or VariableName(pt^.name)
then ExtentedNodeType:='t'
end; {with}
end; { function ExtentedNodeType }
{теперь не уверены, что найдутся правильные атомы!}
{но, в таком случае, обязательно найдется не правильный }
{см. определение ниже в теле процедуры}
procedure FindExtendedAtom(var pt:pNode; var stack: pStack);
var found:Boolean;
begin
with pt^ do
begin
found:=false;
while not found do
begin
UpperType=NodeType(pt);
LeftType= NodeType(left);
RightType=NodeType(right);
if (UpperType<>'f') or (LeftType='Æ') or (RightType='Æ')
then
{дальше искать нечего, формально считаем - найден "не правильный" атом}
found:=true
else if LeftType='f'
then begin push(pt,stack); pt:=pt^.left end
else if RightType='f'
then begin push(pt,stack); pt:=pt^.right end
else {UpperType='f' & LeftType='t' & RightType='t'}
{» найден правильный атом }
found:=true
end; {while}
end; {with }
end; { procedure FindAtom }
{формальное вычисление расширенного элементарного выражения}
function ExtendedAtomVal(root:pExpr):string;
begin
with root^ do
if (ExtendedNodeType(root)='f') and
(ExtendedNodeType(left)='t') and
(ExtendedNodeType(right)='t') {корректный атом}
then ExtendedAtomVal:='x' {сгодиться любой терм!}
else ExtendedAtomVal:='Æ';
end;
function ExpressionCorrect(root:pExpr):boolean;
begin
result:=true;
create(stack);
RootType:=ExtendedNodeType(root);
case RootType of
|
'Æ': result:=false;
'f': push(stack,root);
end;
while (not empty(stack)) and result do
begin
pop(stack,pt);
FindExtendedAtom(pt,stack);
{Формальное "вычисление"}
pt^.Name:=ExtendedAtomValue(pt);
if NodeType(pt)='Æ'
{если результат элементарного вычисления неопределен}
then Result:=false {то результат всего вычисления - и подавно}
else
begin {Сократи дерево}
destroy(pt^.right);
pt^.right:=nil;
destroy(pt^.left);
pt^.left:=nil;
end; {if}
end; {while}
Result:=(NodeType(root)='t')
end;
|
|
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!