Вычислить значение дерева формулы

Содержание

Деревья-формулы
Вычислить значение дерева формулы
Построение бинарного дерева из формулы

Деревья-формулы

7. Формулу вида:
< формула >::= < терминал >( < формула > < знак >< формула >)
< знак >::= +  —  *
< терминал >::= 0123456789
можно представить в виде двоичного дерева (‘дерева – формулы ‘):
— формула из одного терминала (цифры) представляется деревом из одной вершины (корнем) с этим терминалом;
— формула вида ( f1 s f2 ) — деревом, в котором корень – это знак s, а
левое и правое поддеревья – это соответствующие представления f1 и f2 :
а) по заданной формуле построить дерево – формулу, обходя дерево – формулу в 1)прямом, 2)обратном, 3)концевом порядке, напечатать его элементы и вычислить (как целое число) значение.

Мм как бы у меня есть алгоритм только для задания:
пусть в дереве – формуле в качестве терминалов используются не только цифры, но и буквы, играющие роль переменных; преобразовать заданное дерево – формулу, заменяя в нем все поддеревья, соответствующие формулам ( ( f1  f2 ) * f3 ) и ( f1 *( f2  f3 ) ) на поддеревья, соответствующие формулам ( ( f1 * f3)  ( f2 * f3 ) ) и ( ( f1 * f2 )  ( f1 * f3 ) ); распечатать преобразованное дерево в 1)прямом, 2)обратном, 3)концевом порядке;

Помогите преобразовать и исправить ошибки из второго в первое.Сам текст программы:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220

#include #include #include #include #include "dequeLib.h" using namespace std; bool trees_are_equal(btree *one, btree *two) { if (one == NULL) { return two == NULL; } if (two == NULL) { return one == NULL; } if (one->data == two->data)  return false; } int main() { char filename[128]; while (true) { cout  "Enter filename or \"exit\" to quit: "; cin >> filename; if (!strcmp(filename, "exit")) { break; } FILE *fh = fopen(filename, "r"); if (fh == NULL) { cout  "Invalid filename :-("  endl; continue; } btree *tree = build_btree(fh); fclose(fh); btree *d; elem *s; bool tree_changed = false; do  d = tree; s = new_deque(); tree_changed = false; while (d != NULL) { // Обработка :-D if ((d->data == '+'  else if (trees_are_equal(d->left->right, d->right->left)) { delete d->right->left; d->right->left = d->left->left; d->right->data = op; d->left = d->left->right; d->data = '*'; tree_changed = true; } else if (trees_are_equal(d->left->left, d->right->right)) { delete d->right->right; d->right->right = d->right->left; d->right->left = d->left->right; d->right->data = op; d->left = d->left->left; d->data = '*'; tree_changed = true; } else if (trees_are_equal(d->left->right, d->right->right)) { delete d->right->right; d->right->right = d->right->left; d->right->left = d->left->left; d->right->data = op; d->left = d->left->right; d->data = '*'; tree_changed = true; } } // Обход if (d->left != NULL && d->right != NULL) { push(s, 'r', d->right); d = d->left; } else if (d->left == NULL && d->right == NULL) { if (!is_empty(s)) { d = pop(s, 'r'); } else { d = NULL; } } else if (d->left != NULL) { d = d->left; } else { d = d->right; } } delete s; } while (tree_changed); // Распечатка в прямом порядке delete s; d = tree; s = new_deque(); while (d != NULL) { cout  d->data; if (d->left != NULL && d->right != NULL) { push(s, 'r', d->right); d = d->left; } else if (d->left == NULL && d->right == NULL) { if (!is_empty(s)) { d = pop(s, 'r'); } else { d = NULL; } } else if (d->left != NULL) { d = d->left; } else { d = d->right; } } cout  endl; // Распечатка в обратном порядке delete s; d = tree; int F = 1; s = new_deque(); while (F) { while (d != NULL) { push(s, 'r', d); d = d->left; } if (!is_empty(s)) { d = pop(s, 'r'); cout  d->data; d = d->right; } else { F = 0; } } cout  endl; // Распечатка в концевом порядке delete s; d = tree; s = new_deque(); elem *sF = new_deque(); do { while (d != NULL) { push(s, 'r', d); push(sF, 'r', NULL); d = d->left; } if (!is_empty(s)) { do { d = pop(s, 'r'); F = pop(sF, 'r') ? 1 : 0; if (F) { cout  d->data; } } while (F && !is_empty(s)); if (!F) { push(s, 'r', d); push(sF, 'r', d); d = d->right; } } } while (!is_empty(s)); cout  endl; } }

Источник

Вычислить значение дерева формулы

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

1.вычислить значение дерева
2.по формуле из текстого файла f построить дерево
3.напечатать дерево в виде соответствующей формулы, определить высоту заданного дерева.

Мне бы код построения дерева, с остальным я разберусь.

Вообще, хотелось бы знать, соответствующий тип (узел) описан? Если да, то покажите. А то нужно с чего-то начать.

type tnode=^pnode; pnode=record info: char; left, right: tnode; end; var formyla:string; root:tnode;

apostol584, извините, сразу не спросил.
Формат строки-формулы? В каком виде записыватся формула? Как обычно (8+3*5-1)? Или можно использовать упрощенные формы записи типа польской (-+8*351)?

——————————————————————
Короче, будем считать, что запись имеет обычный вид. Как создать дерево из польской записи, думаю и так понятно.

формула вводится в обычном виде, при построении дерева можно использовать любую, а при построении формулы она долна иметь первоночальный вид.

OK
___________________________________ ______________________________
Сразу позволю себе некоторую своевольность.

 PNode = ^TNode; TNode = record Data: Char; Parent: PNode; Left, Right: PNode; end;

Так будет немного помнемоничней
Да и Parent нам пригодится, чтоб не насиловать стек. Хотя можно было и без него

___________________________________ ______________________________
Ща сделаем, но это займет какое-то время. Потому-что доча

Пока незачто
___________________________________ _________________________
70% готовности
— составлена блок-схема (фотку сделать не смог, не нашел SD-карту)
— набросал часть кода

program project1;  uses  cthreads,  Classes, SysUtils, CustApp < you can add units after this >; type PNode = ^TNode; TNode = record Data: Char; Parent: PNode; Left, Right: PNode; end; TCharType = (chtTerm, chtZnak, chtSpace, chtNil, chtError); procedure Error (Mes: String); begin WriteLn (Mes); ReadLn; Halt; end; procedure ErrorInPosition (Pos: Integer); begin Error ('Error in ' + IntToStr(Pos) + ' position'); end; function CharType (const ch: Char): TCharType; begin case ch of '0'..'9' : Result := chtTerm ; '+', '-', '*' : Result := chtZnak ; #9, #10, #13, ' ': Result := chtSpace; #0 : Result := chtNil ; else Result := chtError; end; end; function ZnakVes (const ch: Char): Byte; begin case ch of '+', '-': Result := 1; '*' : Result := 2; else Error ('Invalid argument in ZnakVes (' + ch + ')'); end; end; function NewNode (const ch: Char): PNode; begin New (Result); with Result^ do begin Data := ch; Parent := nil; Left := nil; Right := nil; end; end; function ReadBuf (buf: String): PNode; var Cur, New: PNode; i, Count: Integer; ch: Char; Ojid: TCharType; // признак ожидания begin // подготовка Cur := NewNode (#0); Ojid := chtTerm; Count := Length (buf); for i := 1 to Count do begin // читаем посимвольно ch := buf[i]; case CharType (ch) of chtError, chtNil: ErrorInPosition (i); end; end; Result := Cur; end; function GetFormula (Root: PNode): String; begin if Root = nil then Error ('Invalid argument in GetFormula (nil)') else begin Result := ''; end; end; function CalcFormula (Root: PNode): Integer; begin if Root = nil then Error ('Invalid argument in CalcFormula (nil)') else begin Result := 0; end; end; var Formyla: string; Root: PNode; begin Formyla := '8 + 3*5*4 - 1 + 3*5'; //82 Root := ReadBuf (Formyla); WriteLn (GetFormula (Root), ' = ', CalcFormula (Root)); end.

Источник

Построение бинарного дерева из формулы

Мне бы код построения дерева, с остальным я разберусь.

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

Построение бинарного дерева в «ширину»
Написать процедуру построения бинарного дерева в «ширину», то есть размещать элементы слева направо.

Операции над бинарными деревьями: построение дерева, обход дерева, вставка и удаление элемента дерева
Пожалуйста кто сможет, помогите составить программу: Организация по трудоустройству населения.

Построение бинарного дерева на основе не бинарного
В лабораторной работе есть такое задание: Создайте процедуру построения бинарного дерева на основе.

Построение бинарного дерева. Обход дерева
Построить дерево поиска с элементами – числами. С использованием операций Locate и DeleteLeft найти.

Построение бинарного дерева
Добрый день! Помогите, пожалуйста, написать построение двоичного дерева. На самом деле, нужно.

Построение бинарного дерева
Написать программу построения бинарного дерева с помощью связных структур и поиска в дереве при.

Построение бинарного дерева
День добрый. Написали программу с напарником для задания в универе, но преподаватель требует вывод.

Источник