Скажите пожалуйста этот код строит дерево? - 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;
}

Объяснение кода листинга программы

В данном коде строится дерево вычисления.

  1. В функции BuildTree создается новый узел node и инициализируется указатель n на этот узел.
  2. В n записывается оператор, который является первым элементом в строке s и увеличивается ps для перехода к следующему элементу.
  3. Если оператор n->op равен +, -, * или /, то рекурсивно вызывается функция BuildTree для левого и правого поддеревьев. Результаты этих вызовов записываются в n->left и n->right соответственно.
  4. Если оператор n->op не равен +, -, * или /, то оба поддерева (n->left и n->right) инициализируются как NULL, что означает отсутствие поддеревьев для данного узла.
  5. В конце функции возвращается n, который является вершиной построенного дерева. Таким образом, данный код строит дерево вычисления, где каждый узел представляет собой операцию, а его потомки - операнды этой операции.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.267 из 5
Похожие ответы