#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>

typedef struct node {
    char value;

    struct node *left_c;
    struct node *righ_c;
} nodes;

nodes *init() {
    nodes *nouv = malloc(sizeof(nodes));
    nouv->value = 'E';
    nouv->left_c = NULL;
    nouv->righ_c = NULL;
    return nouv;
}

void addchild(nodes *racine, int x, char value) {
    nodes *nouv = malloc(sizeof(nodes));
    nouv->value = value;
    nouv->left_c = NULL;
    nouv->righ_c =NULL;
    if (x==0) {
        racine->left_c=nouv;
    }
    else {
        racine->righ_c=nouv;
    }
}

int calcno(nodes *racine, nodes *curr, int no) {
    int tmp;

    if (racine == curr)
        return no;
    else {
        if (racine->left_c!=NULL) {
            if ((tmp = calcno(racine->left_c, curr, (no*2))) != -1) {
                return tmp;
                }
        }
        if (racine->righ_c!=NULL) {
            if ((tmp = calcno(racine->righ_c, curr, (no*2)+1)) != -1) {
                return tmp; }
                }
        return (-1);
        }
}

nodes *findfromno(nodes *racine, nodes *curr, int no) {
        nodes *tmp;

        printf("racine recue = %p\tno recu = %d\n", racine, no);

    if (calcno(curr, racine, 1) == no)
        return racine;
    else {
        if (racine->left_c!=NULL) {
            if ((tmp = findfromno(racine->left_c, curr, no)) != NULL) {
                return tmp;
                }
            }
        if (racine->righ_c!=NULL) {
            if ((tmp = findfromno(racine->righ_c, curr, no)) != NULL) {
                return tmp;
                }
            }
        return (NULL);
        }
}

void addnoeud(nodes *racine, int no) {
    int pere;
    nodes *tmp;

    if (no%2==0)
        pere = no/2;
    else
        pere = (no-1)/2;



    tmp = findfromno(racine, racine, pere);

   // printf("pere calculé : %d\nnoeud trouvé : %p\n", pere, tmp);

    if (no%2==0)
        addchild(tmp, 0, 'A');
    else
        addchild(tmp, 1, 'B');
}

int mystrlen(char *str) {
    int k =0;
    while (str[k]!='\0')
        k++;

    return k;
}

char *suppr(char *str){
    char *s = malloc(sizeof(char) *(mystrlen(str)));
    s = strncpy(s, str, mystrlen(str));
    s[(mystrlen(str) -1)] = '\0';
//    printf("%s -> %s\n", str, s);
    return s;
}

void printnode(nodes *racine, char *chemin, int nb, nodes *curr) {
    int hauteur= strlen(chemin) - 1;
//    printf("Chemin: %s\tHauteur: %d\n", chemin, hauteur);
    if (nb == 0) {
        printf("\t %c", racine->value);
        return;
    }
    char *nchemin = malloc(sizeof(char) *(strlen(chemin)+1));
    nchemin = strcpy(nchemin, chemin);
    if (hauteur == nb) {
        printf("\t[%c] %d %p", racine->value, calcno(curr, racine, 1), racine);
    }
    else {
        if (racine->left_c != NULL){
            nchemin = strcat(nchemin, "0");
            printnode(racine->left_c, nchemin, nb, curr);
            nchemin = suppr(nchemin);
        }
        if (racine->righ_c != NULL) {
            nchemin = strcat(nchemin, "1");
            printnode(racine->righ_c, nchemin, nb, curr);
            nchemin = suppr(nchemin);
        }
    }
}

char last(char *str) {
    for (int k=0; k<strlen(str); k++);
    return str[k];
}

int prio(char c1, char c2) {
    char *l ="*/+-"
    int k = 0;
    int k2 = 0;
    while (k<strlen(l) && l[k]!=c1)
        k++;
    while (k2<strlen(l) && l[k2]!=c2)
        k2++;

    return k2-k;

}

char *pol(char *str) {
    int i=0;
    int k=0;



    char *pol="";
    char *pile="";
    while (str[i]!='\0') {

        if (str[i]>='0' && str[i]<='9')
            pol[k++]=str[i];

        if (str[i]=='(')
            pile = strcat(pile, '(');

        if (str[i]=='*' || str[i]=='/' || str[i]=='+' || str[i]=='-') {
            if (strcmp(pile, "")==0 || last(pile)=='(' || prio(str[i], last(pile))>0)
                pile = strcat(pile, str[i]);

        }





    i++;
    }
    return pol;
}

int main()
{
    nodes *racine;
    racine = init();

    char *op = "(2*(5+3))"
}