Cod sursa(job #1852005)

Utilizator RobybrasovRobert Hangu Robybrasov Data 20 ianuarie 2017 13:36:03
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <cstdio>
#include <cstring>
#define MAX_S 100000

using namespace std;

char L[MAX_S];

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

    node(char o = '\0', int v = 0, node *l = NULL, node *r = NULL) :
        left(l), right(r), op(o), val(v) {}
};

int readNumber(char* &p) {
    int n = 0;
    for (; *p >= '0' && *p <= '9'; ++p)
        n = 10 * n + *p - '0';
    return n;
}

const char signs[2][3] = { "+-", "*/"};

/*
 * p - the character we're currently on
 * l - the type of term we're currently examining:
 *     - 0 is a sum
 *     - 1 is a product
 *     - 2 is either a token (i.e. a number or variable) or a parenthesis
 * This function can also be viewed as a multi-purpose function, it's "mode of
 * operation" being set by the value of l. This function is thus nothing more
 * than the trivial combination of the functionalities of the three functions in
 * the indirect recursive implementation.
 */
node *eval(char* &p, int l) {
    node *parent;
    if (l < 2) {
        parent = eval(p, l + 1);
        node *newParent;
        for (; strchr(signs[l], *p); parent = newParent)
            switch (*p) {
                case '+': newParent = new node('+', 0, parent, eval(++p, l + 1)); break;
                case '-': newParent = new node('-', 0, parent, eval(++p, l + 1)); break;
                case '*': newParent = new node('*', 0, parent, eval(++p, l + 1)); break;
                case '/': newParent = new node('/', 0, parent, eval(++p, l + 1)); break;
            }
    } else // Compute the value of a token, which is either a number or a parenthesis
        if (*p == '(') {
            parent = eval(++p, 0);
            ++p;
        }
        else
            parent = new node('\0', readNumber(p));
    return parent;
}

int compute(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
    }
    return 0;
}

int postOrder(node *t) {
    if (t -> left && t -> right) {
        int a = postOrder(t -> left);
        int b = postOrder(t -> right);
//        printf("%c ", t -> op);
        return compute(a, b, t -> op);
    } else {
//        printf("%d ", t -> val);
        return t -> val;
    }
}

int main() {
    FILE *fin = fopen("evaluare.in", "r");
    FILE *fout = fopen("evaluare.out", "w");
    
    fgets(L, MAX_S, fin);
    char *p = L;

    node *T = eval(p, 0);
    
    printf("%d\n", postOrder(T));

    return 0;
}