Structure and Pointers in C: Binary Tree

Asked

Viewed 534 times

0

Hello, I’m trying to create a mathematical expression tree with the following logic:

my expression is a string, and I have 4 character options:

  • ( : When finding this character, my code should create a node for the pref, insert into your conteudo(pref->conteudo) the character '#', save the address of the pref on a dot-type pointer vector called endereco,sum to variable k (causing the vector to walk to the next iteration) and cause pref point to pref->esq.
  • Digits(0 to 9): Creates a node in pref and fills his conteudo(pref->conteudo) with the character of the digit.
  • Operator(+ - * /): When finding an operator, it looks at the last vector address endereco, causes pref = endereco[k] (implicando que pref irá apontar para esse novo endereço) for then pref->conteudo receive the operator character, after that pref = pref->dir(aponta para a direita).
  • ): Decreases the variable k, causing the referential of the vector endereco diminish. In case of ease, I thought of the vector endereco as if it were a pile on its own.

That was my idea, but I’m getting serious segment fault problems even though I can’t think of what I’m missing. The code follows below divided in main and arvbin. c NOTE: My intention was to have a pointer moving through the tree (pm) and something static as a reference for the root, but as I said I’m having serious problems with pointer handling. PS: I noticed in other responses that typedef defining a pointer to a structure is bad programming practice, however this was the only way I could learn to define a pointer to an x structure within that structure.

arvbin. h

#include <stdio.h>
#include <stdlib.h>
#include "arvbin.h"
    typedef struct no *pontNo;
    typedef struct no{
        char conteudo;
        pontNo esq;
        pontNo dir;
    }no;
    void CRIA_NO(pontNo novoNo,char info){
        novoNo = malloc(sizeof(no));
        novoNo->conteudo = info;
        novoNo->esq = NULL;
        novoNo->dir = NULL;

    }

main. c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arvbin.h"



int main() {
    //Declaracao de variaveis & Inicializacoes:
    no raiz; //Raiz da arvore declarada
    raiz.conteudo = '#'; //Declarando conteudo da raiz
    pontNo pm = &raiz; //(P)onteiro para (M)ovimentacao na arvore,inicialmente apontando para raiz
    pontNo endereco[20]; //Vetor de ponteiros para endereco do tipo pontNo, funcionara como uma pilha
    char expressao[100]; //Expressao matematica inserida
    int resultado;

    //Funcionamento:
    while(1){
        printf("Escreva a expressao matematica(Caso queira parar, escreva 0): ");
        scanf("%s",expressao);
        if(strcmp(expressao,"0") == 0) break; //Condicao de parada do loop de insercao de expressoes
        int k = 0;
        int error = 0;
        int i;      
        for(i = 0;expressao[i] != '\0';i++){
            if(expressao[i] == '('){
                if(i == 0){
                    endereco[k] = pm;
                    printf("%c\n",endereco[k]->conteudo);
                    k++;
                    pm = pm->esq;
                }
                else{
                    CRIA_NO(pm,'#');
                    endereco[k] = pm;
                    printf("%c\n",endereco[k]->conteudo);
                    k++;
                    pm = pm->esq;                   
                }
            }
            else if(expressao[i] == '0'||expressao[i] == '1'||expressao[i] == '2'||expressao[i] == '3'||expressao[i] == '4'||expressao[i] == '5'||expressao[i] == '6'||expressao[i] == '7'||expressao[i] == '8'||expressao[i] == '9'){
                    CRIA_NO(pm,expressao[i]);
                    printf("%c\n",pm->conteudo);                    
            }
            else if(expressao[i] == '+'||expressao[i] == '-'||expressao[i] == '*'||expressao[i] == '/'){

            }
            else if(expressao[i] == ')'){

            }
            else{
                printf("Erro na expressao: char nao reconhecido!\n");
                error = 1;
                break;
            }
        }

    }
    return 0;
}

If you have another way to solve this problem, let me know!

  • What is the entrance to that tree ? I see a if for a numeric digit, and how are you interpreting numbers with more than 1 digit ? Try to make your logic clearer by giving examples of input and output values with the respective explanation of the applied logic.

  • Only 1 digit values will enter, in case the input is a string of expressions ex: (2+3), in the for loop I check each item of the string expression

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.