Building parse tree from prefixed expression in c

Question

I'm trying to create a binary tree like this: link

The input will be entered by the user as prefix and read as a string, then put in a binary tree.

This is what I have so far:

struct node{
   char val;
   struct node *left;
   struct node *right;
};
typedef struct node root;
typedef root *tree;

In main:

void main(){
    int i;
    tree tr;
    char* s;
    s=input(); //input function
    tr=create_empty_tree(); 
    for(i=0;s[i]!='\0';i++){
        tr=add_root(s[i],ab);
    }
    convert_infix(tr);
}

and this is the part I've been struggling with for days; I can't seem to build the tree correctly. This is what I have so far:

tree add_root(char val, tree tr){
    if ( tr == NULL ){
        tr= create_root(val);
    }
    else{
        if(val=="*" || val=="+" || val=="-" || val=="/"){
            tr->left= add_root(val, tr->left);
        }
        else{
            if(tr->left == NULL){
                tr->left= add_root(val, tr->left);
            }
            else{
                tr->right= add_root(val, tr->right);
            }
        }
    }
    return tr;
}

I looked this up online and I know that my function is wrong, I tried doing this:

• Insert new nodes, each time moving to the left until an operand has been inserted.

• Backtrack to the last operator, and put the next node to its right.

• Continue in the same pattern.

but I don't know how to backtrack. I've been at this for days and I'm going crazy; I'm just a beginner in programming so please don't judge.

Answer 1

Simple sample(Error checking has been simplified)

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

struct node{
   char op;
   int val;
   struct node *left;
   struct node *right;
};

typedef struct node Tree;

char *get_token(char **p){
    while(**p && isspace(**p)){//skip spaces
        ++*p;
    }
    char *ret = *p;
    if(!*ret){//empty
        return NULL;
    }
    while(**p && !isspace(**p)){
        ++*p;
    }
    if(!**p){
        **p = 0;
        ++*p;
    }
    return ret;
}

Tree *make_tree(char **p){
    char *token = get_token(p);

    if(token){
        Tree *tree = malloc(sizeof(*tree));

        switch(*token){//token[1] == '\0' ??
        case '*':
        case '/':
        case '+':
        case '-':
            tree->op = *token;
            tree->val = 0;
            tree->left = make_tree(p);
            tree->right = make_tree(p);
            break;
        default:
            tree->op = 'N';
            tree->val = atoi(token);
            tree->left = tree->right = NULL;
        }
        return tree;
    }
    return NULL;
}

void release(Tree *tree){
    if(tree){
        release(tree->left);
        release(tree->right);
        free(tree);
    }
}

void print_infix(Tree *tree){
    if(tree){
        switch(tree->op){
        case '*':
        case '/':
        case '+':
        case '-':
            putchar('(');print_infix(tree->left);printf(" %c ", tree->op);print_infix(tree->right);putchar(')');
            break;
        case 'N':
            printf("%d", tree->val);
            break;
        default:
            fprintf(stderr, "\nerror!\n");//this should never be executed
        }
    }
}

int main(void){
    char line[256];

    while(fgets(line, sizeof(line), stdin)){
        char *s = line;
        Tree *tree = make_tree(&s);
        print_infix(tree);
        putchar('\n');
        release(tree);
    }
    return 0;
}
#if 0
* + 7 3 - 5 2
((7 + 3) * (5 - 2))
* 3 + 1  2
(3 * (1 + 2))
/ + 1 + 2 3 5
((1 + (2 + 3)) / 5)
^Z
#endif

Answer 2

you have a problem here, a char is not a string char* so you can't do something like make a comparison between a char and a char *...... '' is used for char when "" is used for c string i.e char * so replace this:

    if(val=="*" || val=="+" || val=="-" || val=="/")

by the following code

    if(val=='*' || val=='+' || val=='-' || val=='/')