从c中的前缀表达式构建解析树 [英] Building parse tree from prefixed expression in c

问题描述

我正在尝试创建一个二叉树： link

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;

主要：

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.

继续在同一个

但我不知道如何回溯。
我一直在这几天，我要疯了，我只是编程的初学者，请不要判断。

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.

推荐答案

简单示例（错误检查已被简化） / p>

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

这篇关于从c中的前缀表达式构建解析树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！