Текст программы. 7 Используемые переменные. 7. Структура узла бинарного дерева. 7. Функция создания дерева. 7 — страница 2

  • Просмотров 223
  • Скачиваний 5
  • Размер файла 57
    Кб

толкаем в стек; Если оператор имеет равный или меньший приоритет вычисления, чем оператор на вершине стека, то выталкиваем оператор из стека в результат, и толкаем в стек новый оператор; Достигнув на входе % – остановочный оператор, выталкиваем все из стека, пока не дойдем до %. Стек – это специальная область памяти, представляющая собой очередь типа «последним пришел – первым вышел». Алгоритм вычисления префиксной формы записи

реализуется следующим образом: Имеем на входе формулу в инфиксной форме: a+b/(c-d); Перепишем формулу справа налево: (d-c)/b+a; Воспользуемся алгоритмом постфиксной трансляции, получим: dc-b/a+; Полученную формулу перепишем справа налево, получим формулу в префиксной записи: +a/b-cd. Все описанные алгоритмы (перевод в постфиксную и префиксную форму записи) реализованы в программе, написанной на объектно-ориентированном языке

программирования Borland C++ Builder 4. 2. 2. Текст программы. 2 . 2. 1. Используемые переменные. char formula[100]=""; char resultat[100]=""; char temp_formula[100]=""; char turn_formula[100]=""; int b=0, k, i=0, t=0, j=0; 2 . 2. 2. .Структура узла бинарного дерева. struct node { char op; node *left,*right; }; 2 . 2. 3. .Функция создания дерева. node * BuildTree(char s[],int & ps){ node * n=new node; n->op=s[ps++]; if(n->op=='+'||n->op=='-'||n->op=='*'||n->op=='/') { n->left=BuildTree(s,ps); n->right=BuildTree(s,ps); } else n->right=n->left=NULL; return n; } 2 . 2. 4. .Функция вывода дерева.

void PrintTree(node * p,int lev=0){ if(p==0) return; PrintTree(p->left,lev+1); Form1->Memo1->Lines->Add(""); for(int i=0;i<lev;i++) Form1->Memo1->Text=Form1->Memo1->Text+" "; Form1->Memo1->Text=Form1->Memo1->Text+p->op; PrintTree(p->right,lev+1); } 2 . 2. 5. .Функции, реализующие стек. const int maxsize=50; char values[maxsize]; int top=0; bool empty() { if (top==0) return true; else return false; } void push(char c) { if (top==maxsize) ShowMessage("Overflow in stack!!!"); else values[top++]=c; } void pop(char &c) { if (empty()) ShowMessage("Stack is empty!!!"); else c=values[--top]; } 2 . 2. 6. .Функция перевода в постфиксную форму

записи. void PostFix(char *in, char *res) { int i=0; int n_r=0; char c, temp; push('%'); while (in[i]!='%') { c=in[i++]; if (c=='(') {push(c); continue;} if (c==')') { pop(temp); while (temp!='(') { res[n_r++]=temp; pop(temp); } continue; } if (c=='+'||c=='-') { pop(temp); if (temp=='%'||temp=='(') { push(temp); push(c); } else if (temp=='+'||temp=='-'||temp=='*'||temp=='/') { res[n_r++]=temp; push(c); } continue; } if (c=='*'||c=='/') { pop(temp); if (temp=='%'||temp=='('||temp=='+'||temp=='-') { push(temp); push(c); } if (temp=='*'||temp=='/') { res[n_r++]=temp; push(c); } continue; } else res[n_r++]=c; } pop(temp); while (temp!='%') { res[n_r++]=temp; pop(temp); } } 2 . 2. 7. . Алгоритм перевода в префиксную форму записи. //

Определяем количество символов в формуле i=0; while (formula[i]!='%') { k=i; i++; } // Реверсируем формулу справа налево for (i=k; i>=0; i--) { if (formula[i]=='(') temp_formula[j]=')'; else if (formula[i]==')') temp_formula[j]='('; else { temp_formula[j]=formula[i]; t++; } j++; } j=0; // Добавляем остановочный символ - % temp_formula[++k]='%'; // Обнуляем resultat for (i=0; i<=100; i++) resultat[i]=NULL; // Запускаем алгоритм постфиксного преобразования PostFix(temp_formula, resultat); // Реверсируем формулу обратно справа налево и получаем формулу в префиксной