Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Бинарное дерево

Автор: Holop 6.6.2004, 06:55

Помогите люди добрые! Нужно написать прогу на С++ builder. Вводишь формулу в инфиксной форме. Например: (a+b)*(f-g) Строится бинарное дерево: * + - a b f g И через обход потом этого дерева выводится в префиксной форме: *+ab-fg (произведение суммы a и b с разностью f и g).

Автор: dargaard 6.6.2004, 10:20

Код // author : dargaard // // CFG: // Expr    -> term + expr //         -> term - expr //         -> term // Term    -> factor * term //         -> factor // Factot  -> id //         -> ( expr ) // // // ispolzovanie   v inpute  (a+b)*c-d*r i t.d. // probeli ne razresheni // #include <stdio.h> #include <stdlib.h> // // struktura dlia dereva // struct _node {        int chr;        struct _node *left;        struct _node *right; }; char inp[100]; int inp_ptr; int tok; void musthave (char); int get_token (); struct _node* parse_input(); struct _node* parse_expr (); struct _node* parse_term (); struct _node* parse_factor (); struct _node* parse_R1 (); void show_tree(struct _node* cur); struct _node *root; int main() {        struct _node *cur;        inp_ptr = 0;        scanf("%s",inp);        root = parse_input ();        printf("\n\n");        cur = root;        show_tree(root);        printf("\n"); } // // vivod dereva // void show_tree(struct _node* cur) {        if (cur->chr!=0) printf(" %c ",cur->chr);        if (cur->left!=0) show_tree(cur->left);        if (cur->right!=0) show_tree(cur->right); } // // parsim input // struct _node* parse_input () {        tok = get_token ();        return parse_expr (); } // // parsim expr (smotri vishe) // struct _node* parse_expr ()  {        struct _node *new_node = malloc(sizeof(struct _node));        new_node->left = 0;        new_node->chr = 0;        new_node->right = 0;        new_node->left = parse_term ();        //        // Expr -> Term + Expr | Term - Expr        //        if (tok == '+') {                new_node->chr = '+';                musthave ('+');                printf(" + ");                new_node->right = parse_expr ();        } else if (tok == '-') {                new_node->chr = '-';                musthave ('-');                printf (" - ");                new_node->right = parse_expr ();        }        return new_node; } // // parsim term // struct _node* parse_term () {        struct _node *new_node = malloc(sizeof(struct _node));        new_node->chr =0;        new_node->left =0;        new_node->right =0;        //        // Term -> Factor | Factor * Term        //        new_node->left = parse_factor ();        tok = get_token ();        if (tok == '*') {                new_node->chr = '*';                musthave ('*');                printf (" * ");                new_node->right = parse_term ();        }        return new_node; } // // Factor -> id | ( Expr ) // struct _node* parse_factor () {        struct _node *new_node = malloc(sizeof(struct _node));        new_node->left = 0;        new_node->chr = 0;        new_node->right = 0;        if (is_id(tok)) {                printf("|%c|",tok);                new_node->chr = tok;        } else {                musthave ('(');                printf (" ( ");                new_node->left=parse_expr ();                printf (" ) ");                //tut musthave nenuzhno uzhe                //musthave (')');        }        return new_node; } // // poluchaem novii token // int get_token () {        inp_ptr++;        return inp[inp_ptr-1]; } void musthave(char c) {        if (c != tok) {                printf("Error musthave %c got %c\n",c,tok);                exit(0);        }        tok = get_token (); } int is_id (int c) {        if (c >= 'a' && c <= 'z') return 1;        return 0; } деление не сделанно написано под linux но на winde тоже должно работать.

Автор: Holop 9.6.2004, 06:57

Спасибо большое!

Автор: dargaard 12.6.2004, 19:51

В прошлый раз как то криво написал Вот более нормальная версия где деление работает Код // // Example input: a+b+c/(a-e/f+g*a+(b/c)) // #include <stdio.h> #include <stdlib.h> // // Tree struct // struct node {    char chr;    struct node *left;    struct node *right; }; char next_tok; char inp[100]; int inp_ptr=0; char get_token (); void scan (); void mustHave (char ); int is_id (char); struct node* parse_input (); struct node* parse_expr (); struct node* parse_expr2 (); struct node* parse_expr3 (); struct node* parse_expr4 (); void show_tree (struct node*); int main () {        struct node* root;    scanf ("%s",inp);    root = parse_input();    printf("\n");    show_tree(root);    printf ("\n\n\n"); } // // show binary tree // void show_tree(struct node* cur) {    if (cur->chr!=0) printf(" %c ",cur->chr);    if (cur->left!=0) show_tree(cur->left);    if (cur->right!=0) show_tree(cur->right); } // // Get next token (next char) // char get_token () {    inp_ptr++;    return inp[inp_ptr]; } // // set next_tok to next token // void scan () {    next_tok = get_token (); } void mustHave(char c) {    if (next_tok == c) {        scan ();    } else {        printf("Parse Error: expected %c got %c\n",c,next_tok);        exit (-1);    } } // // allocate memory for new node // struct node* malloc_node () {    struct node* nnode = malloc(sizeof(struct node));    nnode->chr = 0;    nnode->left = 0;    nnode->right = 0;    return nnode; } // // parse input // struct node* parse_input () {    next_tok = inp [0];    return parse_expr (); } // // parse expression // // expr -> expr2 { ('+' | '-') expr2 } // struct node* parse_expr () {    struct node* new_node = malloc_node ();    struct node* old=0;    new_node->left = parse_expr2 ();    while (1) {        if (next_tok == '+') {            scan ();            new_node->chr = '+';            printf(" + ");            new_node->right = parse_expr2 ();        } else if (next_tok == '-') {            scan ();            printf(" - ");            new_node->chr = '-';            new_node->right = parse_expr2 ();        } else {            break;        }        old = new_node;        new_node = malloc_node ();        new_node->left = old;    }    return new_node; } // // parse expression // // expr2 --> expr3 { ('*' | '/') expr3 } // struct node* parse_expr2 () {    struct node* new_node = malloc_node ();    struct node* old = 0;    new_node->left = parse_expr3 ();        while (1) {        if (next_tok == '*') {            scan ();            printf (" * ");            new_node->chr = '*';            new_node->right = parse_expr3 ();        } else if (next_tok == '/') {            scan ();            printf (" / ");            new_node->chr = '/';            new_node->right = parse_expr3 ();        } else {            break;        }        old = new_node;        new_node = malloc_node ();        new_node->left = old;    }    return new_node; } // // parse expression // // expr3 --> ('+' | '-') expr3 //       --> expr4 // struct node* parse_expr3 () {        struct node* new_node=malloc_node ();        if (next_tok == '+') {            scan ();            printf (" u+ ");            new_node->chr = '+';            new_node->left = parse_expr3 ();                    } else if (next_tok == '-') {            scan ();            printf (" u- ");            new_node->chr = '-';            new_node->left = parse_expr3 ();        } else {            new_node->left = parse_expr4 ();        }    return new_node; } // // parse expression // // expr4 --> ( expr ) //       --> ID // struct node* parse_expr4 () {    struct node* new_node = malloc_node ();    if (next_tok == '(') {        printf (" ( ");        scan ();        new_node->left=parse_expr ();        mustHave (')');        printf (" ) ");    } else if (is_id(next_tok)) {        printf ("|%c|",next_tok);        new_node->chr = next_tok;        scan ();    }    return new_node; } int is_id (char c) {    if (c>='a' && c<='z') return 1;    return 0; }

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)