VPF::Бинарное дерево - Форум программистов

Holop

Дата 6.6.2004, 06:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 6.6.2004

Репутация: нет
Всего: нет

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

a b f g

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

dargaard

Дата 6.6.2004, 10:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Экс. модератор
Сообщений: 450
Регистрация: 7.5.2004

Репутация: 4
Всего: 25

Код


// 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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 6.6.2004

Репутация: нет
Всего: нет

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

dargaard

Дата 12.6.2004, 19:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Экс. модератор
Сообщений: 450
Регистрация: 7.5.2004

Репутация: 4
Всего: 25

В прошлый раз как то криво написал

Вот более нормальная версия где деление работает

Код


//
// 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;
}

--------------------

Ты должна сделать добро из зла
потому что его больше не из чего
сделать. Р.П.Уоррен

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »