Практикум. Разбор арифметических выражений с использованием бинарных деревьев

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

Одним из способов разбора выражения является представление его в виде дерева, каждое под дерево которого отображает одну операцию выражения в порядке убывания приоритета операции. В корнях такого дерева хранится знак операции, а каждое поддерево представляет собой операнд. Так, например, выражение

(х+1,5)(х-10)(Х+5У(Х'31)

может быть представлено бинарным деревом, изображенным на рис. 7.25 (возведение в степень обозначено символом «Л»).

Построение дерева выражения выполняется следующим образом:

а) в символьной строке, содержащей запись выражения, определяется положение операции с минимальным приоритетом, записанной вне круглых скобок (если строка содержит несколько операций одинакового приоритета, то выбираем любую из них);

б) операция записывается в корень дерева, а строка делится на две: подстрока первого операнда и подстрока второго операнда, при этом по необходимости выполняется операция снятия скобок;

в) в подстроках операндов вновь определяется положение операции с минимальным приоритетом и т.д.

Если полученные на очередном шаге подстроки не содержат операций, то процесс заканчивается, а подстроки записываются в вершины очередного уровня в качестве листьев.

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


выполняется рекурсивно:

• если вершина - лист, то в качестве результата подставляется значение константы или переменной,

• если вершина - операция, то вычисляется левый операнд, потом - правый операнд, а затем над ними выполняется операция.

Правила работы с деревом выражения легко можно дополнить так, чтобы обеспечить вычисление элементарных функций, таких, как sin х или 1п х. Например, имя функции будем записывать в соответствующей вершине дерева, а аргумент представлять в виде левого поддерева. Выражение (x+l,5)*cos(2*x+5), таким образом, будет представлено деревом, изображенным на рис. 7.26.

Пример 7.7. Разработать программу построения таблицы значений функции одного аргумента, определенной пользователем. (Чтобы не усложнять и без того сложную программу, не будем предусматривать операцию «унарный минус».)

В первую очередь определим структуру информационной части записи, соответствующей вершине дерева: каждая вершина должна хранить знак операции, адреса операндов и для констант - значение константы, причем для листьев в качестве знака операции будет храниться признак типа листа: «о» - константа или «х» - переменная.

Процедура Constr_Tree конструирования дерева из выражения по сути рекурсивна: она последовательно должна разбивать строку выражения на отдельные операции и строить соответствующие поддеревья. Параметры процедуры: адрес корня дерева г и строка выражения, из которой необходимо построить дерево. Процедура должна многократно осуществлять поиск разделяющего знака операции: сначала нижнего уровня приоритета, затем все более высокого. Этот поиск целесообразно реализовать как внутреннюю функцию, которая будет получать множество знаков операции Set_Of и строку st.

Вычисление выражения по дереву также будет выполняться рекурсивной функцией Count. Эта функция в качестве параметров будет получать значение адрес корня дерева и значение х. При вычислении учтем, что выполнение некоторых операций, например деления на ноль, получение логарифма отрицательного числа и т.п., невозможно; в этом случае функция Count будет возвращать значение параметра Key=false.

Program ex;

Type setChar=set of char; (тип «множество символов»} str80=string[80]; (тип «строка длиной 80 символов»} рТор^Тор; (тип «указатель на вершину»}

Top-record {тип «вершина»}

operator:string[5]; {знак операции} ,

value:single; {значение константы}

left,right:pTop; {указатели на левое и правое поддерево} end;

Var st:str80; {строка - запись выражения}

RooUpTop; {корень дерева выражения}

key:boolean; {признак существования значения в заданной точке}

x,xnfxe,dx,y:single; {начальное, конечное значения и шаг

аргумента, значение аргумента и функции} n,i:word; {количество точек и номер текущей точки} {рекурсивная функция конструирования поддерева

выражения с корнем г из строки st}

Procedure Constr_Tree(r:pTop;st:str80);

Var nexVpTop; SetOp.

setChar; po,code:integer; stl,stri:str80; c:single;

{внутренняя функция поиска разделительного знака в строке st:

SetOp - множество знаков; функция возвращает позицию разделительного знака или 0}

Function PosOp(st:str80;SetOp:setChar):byte;

Var i,j,k,p:byte; begin

j:=0; k:=0; p:-0; i:=l; while (i< = length(st)) and (p=0) do begin

ifst[i]= T then inc(j) {считаем количество

открывающихся скобок} else if st[i]= ’) ’ then inc(k) {считаем количество

закрывающихся скобок} else if (/=к) and (st[ij in SetOp) then p:=i;

inc(i);

end;

PosOp:=p;

end;

{раздел операторов функции конструирования дерева выражения}

Begin

ро: =PosOp(st,[‘+ ’]); {ищем разделительный знак операции + или -} ifро=0 thenpo:=PosOp(st,[‘*\’/’]); {ищем разделительный знак

операции * или /}

ifpo=0 then ро: =PosOp(st,[‘A ’]); {ищем разделительный знак операции Л} ifpo0then {разделяющий знак найден}

begin

/Лoperator:=st[poJ; {записываем знак операции в вершину} stl:=copy(st,l,po-l); {копируем подстроку первого операнда}

if(stl[l]='(‘) and (PosOp(stl,[‘*\ ’+ ’ ’А’])=0) then

stl: =copy(stl,2,length(stl)-2); {убираем скобки}

stri: =copy(st,po+1,length(st)-po); {копируем подстроку второго операнда}

if (slri[lJ='() and (PosOp(stri,[‘*\ ’+ ’A’])=0) then

stri:=copy(stri,2,length(stri)-2); {убираем скобки} new(rA.left); {создаем левое поддерево}

Constr_Tree(rA.left,stl); {конструируем левый операнд}

new(rA.right); {создаем правое поддерево}

Constr_Tree(rt'.right,stri); {конструируем правый операнд} end else

if st[l]= ’x ’ then {аргумент} begin

rA. operator: = ’x ’;

rA. left: =nil; rA.right:=nil; end

else

. begin

val(st,c,code); {пытаемся получить число} if code=0 then {константа} begin

rA.operator:~’o’; гЛ. left: =nil; rA. right: =nil; rA. Value: =c; end

else {функция}

begin

po:=Pos(‘(‘,st);

rA.operator: = copyist,l,po-l); {выделяем имя функции} rA.right:=nil;

stl:=copy(st,po+l,length(st)-po-l); {выделяем подстроку

параметра}

new (rA.left);

. Constr_Tree(rA.left,stl); {конструируем параметр}

end; end; end;

{рекурсивное вычисление значения функции: если Key=false, то значение не существует}

Function Count(r:pTop;x:single;Var key .boolean)-.single;

Var s,si . single; begin

if not key then {значение функции не существует}

begin

Count:-0; exit; end;

if гл. operator = ’o ’ then

Count: =rA. Value {константа}


if rA.operator= ’x ’ then

Count: =x {переменная x}

else

case rA. operator[l] of

'+ V Count: =Count(rA.left.x,key)+Count(rA.right,x,key);

Count: =Count(rA. left,х,key) - Count (rA.right,x,key); '*’: Count:=Count(rA.left,x,key)*Count(rA.right,x,key); '/’: begin

s: =Count(rA. right,x, key); if abs(s)

<< | >>
Источник: Иванова Г.С. Основы программирования. 2002

Еще по теме Практикум. Разбор арифметических выражений с использованием бинарных деревьев:

  1. 3. Равнение на среднее арифметическое.
  2. 3. Разбор последствий
  3. 3. Разбор ключевых понятий
  4. 5. Разбор шизофренических расстройств по Е. Блейлеру
  5. Аналитический разбор причин госпитализации
  6. 3.11.10. Облако и Дерево
  7. О друзьях-деревьях
  8. Построение дерева целей.
  9. Дерево упало
  10. Психологический практикум (к части II)
  11. Психологический практикум (к части I)
  12. Психологический практикум (к части IV)
  13. Часть III. Клинико-экзистенциальное описание и разбор случаев из практики
  14. Психологический практикум (к части III)
  15. Над деревьями
  16. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации