Cod sursa(job #590456)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 17 mai 2011 16:55:22
Problema Evaluarea unei expresii Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <string.h>

#define MAX_LEN 100000

#define IS_OPERATOR(x) ((x) == '+' || (x) == '-' || (x) == '*' || (x) == '/')

char ops[2][3] = {"+-", "*/"};
char c[MAX_LEN];
char *p;

typedef struct _node_t {
    int value;
    char op;
    _node_t *left;
    _node_t *right;

    _node_t(char o = ' ', int v = 0, _node_t *l = NULL, _node_t *r = NULL)
    {
        op = o;
        value = v;
        left = l;
        right = r;
    }
}node_t;

node_t *root;

node_t* form_tree(int level)
{
    node_t *x = NULL, *y = NULL;

    if (level > 2)
        return NULL;

    if (strlen(p) == 0)
        return NULL;

    if (level == 2)
    {
        if (*p == '(')
        {
            p++;
            x = form_tree(0);
            p++;
        } else {            
            x = new node_t(' ', *p - '0');
            p++;
        }
    }
    else
    {
        for (x = form_tree(level + 1); strlen(p) && strchr(ops[level], *p); x = y)
            y = new node_t(*p++, 0, x, form_tree(level + 1));
    }

    return x;
}

int eval_tree(node_t *node)
{
    if (node == NULL)
        return 0;

    if (IS_OPERATOR(node->op))
    {
        int v1 = eval_tree(node->left);
        int v2 = eval_tree(node->right);

        switch (node->op)
        {
            case '+':
                return v1 + v2;
            case '-':
                return v1 - v2;
            case '*':
                return v1 * v2;
            case '/':
                return v1 /v2;
            default:
                return 0;
        }
    } else
        return node->value;
}

void delete_tree(node_t *node)
{
    if (node == NULL)
        return;

    delete_tree(node->left);
    delete_tree(node->right);

    delete node;

    node = NULL;
}

int main()
{
    node_t *node = root;

    freopen("evaluare.in", "r", stdin);
    freopen("evaluare.out", "w", stdout);

    fgets(c, sizeof(c), stdin);
    p = &c[0];

    root = form_tree(0);

    printf("%d", eval_tree(root));
    
    delete_tree(root);

    return 0;
}