Скажите пожалуйста этот код строит дерево? - C (СИ)
Формулировка задачи:
Что то я не пойму он стороит дерево или просто связанные списки
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct ListElem
{
int data;
struct ListElem* next;
};
struct List
{
struct ListElem* head;
struct ListElem* tail;
int size;
};
struct List* createList()
{
struct List* r = malloc(sizeof(struct List));
r->head = NULL;
r->tail = NULL;
r->size = 0;
return r;
}
int strToInt(char str)
{
int chislo=0;
chislo = str - 48;
return chislo;
}
void addFirst(struct List* a,int x)
{
struct ListElem* e = malloc(sizeof(struct ListElem));
e->data = x;
e->next = a->head;
a->head = e;
if(a->size == 0)
a->tail = e;
a->size++;
}
void addTail(struct List* l,int x)
{
struct ListElem* a = malloc(sizeof(struct ListElem));
a->data = x;
a->next = NULL;
if(l->size == 0)
l->head = a;
else
l->tail->next = a;
l->size++;
l->tail = a;
}
int size(struct List* l)
{
return l->size;
}
int delFirst(struct List* l)
{
int ch = l->head;
struct ListElem* phead = l->head;
l->head = l->head->next;
free(phead);
l->size--;
return ch;
}
int delTail(struct List* l)
{
int ch;
struct ListElem* a = l->head;
int i;
if(l->size == 1)
{
ch = a->data;
free(a);
l->size = 0;
}
else
{
for(i=0;i<l->size-2;i++)
a = a->next;
l->tail = a;
ch = a->next->data;
free(a->next);
l->size--;
}
return ch;
}
int getElem(struct List* l,int index)
{
struct ListElem* a = l->head;
int i;
for(i=0;i<index;i++)
a = a->next;
return a->data;
}
int strLen(char* c)
{
char* p = c;
while(*p++);
return (p-(c+1));
}
int prioritet(char ch)//Возвращает приоритет операции
{
if((ch == '+')||(ch == '-'))
return 1;
if((ch == '*')||(ch =='/'))
return 2;
}
int findPriorPredElem(struct List* a,int index)//Возвращает приоритет предыдущего элемента
{
struct ListElem* p;
int i;
p = a->head;
for(i=0;i < index - 1;i++)
p = p->next;
return prioritet((char)p->data);
}
int arnost(char op)
{
if((op == '+')||(op == '-')||(op == '*')||(op == '/'))
return 2;
}
int operResult(struct List* stack,char operation)
{
int i;
double result = 0;
int fop,sop;
if(operation == '+')
result = (delTail(stack)) + (delTail(stack));
if(operation == '*')
result = (delTail(stack)) * (delTail(stack));
if(operation == '-')
{
sop = (delTail(stack));
fop = (delTail(stack));
result = fop - sop;
}
if(operation == '/')
{
sop = (delTail(stack));
fop = (delTail(stack));
result = fop / sop;
}
return result;
}
struct List* strToRPN(char* str)
{
struct List* quene;
struct List* operation;
int i;
quene = createList();
operation = createList();
for(i=0;i<strLen(str);i++)//Цикл чтения входной строки
{
if((str[i]>=48)&&(str[i]<=57))
addFirst(quene,(int)str[i]);
else
{
if((operation->size > 0)&&(prioritet(str[i]) < findPriorPredElem(operation,operation->size)))
addFirst(quene,delTail(operation));
addTail(operation,(int)str[i]);
}
}
while(operation->size > 0)
addFirst(quene,delTail(operation)); //Проблема при перекидывании последнего плюса(проблема в delTail(исправлено))
return quene;
}
int RPNToResult(struct List* quene)
{
struct List* stack;
int tmpResult;
int i,arn,ret_getElem;
stack = createList();
for(i=quene->size - 1;i >= 0;i--)
{
ret_getElem = getElem(quene,i);
if((ret_getElem >= (int)'0')&&(ret_getElem <= (int)'9'))
addTail(stack,strToInt(ret_getElem));
else
{
addTail(stack,operResult(stack,ret_getElem));
}
}
return delTail(stack);
}
int main()
{
struct List* ochred;
int i;
ochred = strToRPN("1+2+3+4*5+9");
for(i = ochred->size - 1;i >= 0;i--)
printf("%c",getElem(ochred,i));
printf("\n");
printf("%d",RPNToResult(ochred));
getch();
return 0;
}Решение задачи: «Скажите пожалуйста этот код строит дерево?»
textual
Листинг программы
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;
}
Объяснение кода листинга программы
В данном коде строится дерево вычисления.
- В функции
BuildTreeсоздается новый узелnodeи инициализируется указательnна этот узел. - В
nзаписывается оператор, который является первым элементом в строкеsи увеличиваетсяpsдля перехода к следующему элементу. - Если оператор
n->opравен+,-,*или/, то рекурсивно вызывается функцияBuildTreeдля левого и правого поддеревьев. Результаты этих вызовов записываются вn->leftиn->rightсоответственно. - Если оператор
n->opне равен+,-,*или/, то оба поддерева (n->leftиn->right) инициализируются какNULL, что означает отсутствие поддеревьев для данного узла. - В конце функции возвращается
n, который является вершиной построенного дерева. Таким образом, данный код строит дерево вычисления, где каждый узел представляет собой операцию, а его потомки - операнды этой операции.