Cod sursa(job #1439599)

Utilizator radarobertRada Robert Gabriel radarobert Data 22 mai 2015 19:39:50
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

struct Edge{int order, sign, priority, x1, x2, left, right;};
Edge edges[50001];
int id[50001];

int compare(const void *a, const void *b)
{
    int comp = -1 * (edges[*(int*)a].priority - edges[*(int*)b].priority);
    if (comp != 0)
        return comp;
    return edges[*(int*)a].order - edges[*(int*)b].order;
}

int makeEdges(char *input)
{
    int input_size = strlen(input);
    int left_nr = 0;
    int sign = 1;
    int sign_priority = 1;
    int current_priority = 0;
    int n = 0;
    for (int i = 0; i < input_size; i++)
    {
        switch(input[i])
        {
        case '(':
            current_priority += 3;
            break;
        case ')':
            current_priority -= 3;
            break;
        case '+':
            sign = 1;
            sign_priority = current_priority + 1;
            break;
        case '-':
            sign = 2;
            sign_priority = current_priority + 1;
            break;
        case '*':
            sign = 3;
            sign_priority = current_priority + 2;
            break;
        case '/':
            sign = 4;
            sign_priority = current_priority + 2;
            break;
        case '%':
            sign = 5;
            sign_priority = current_priority + 2;
            break;
        case '^':
            sign = 6;
            sign_priority = current_priority + 3;
            break;
        default:
            int x = input[i] - '0';
            while (input[i+1] >= '0' && input[i+1] <= '9')
            {
                i++;
                x = x * 10 + (input[i] - '0');
            }
            ++n;
            edges[n].x1 = left_nr;
            edges[n].x2 = x;
            edges[n].priority = sign_priority;
            edges[n].sign = sign;
            edges[n].left = n-1;
            edges[n].right = n+1;
            edges[n].order = n;
            left_nr = x;
            break;
        }
    }
    return n;
}

int compute(Edge e)
{
    int t;
    switch (e.sign)
    {
    case 1:
        t = e.x1 + e.x2;
        break;
    case 2:
        t = e.x1 - e.x2;
        break;
    case 3:
        t = e.x1 * e.x2;
        break;
    case 4:
        t = e.x1 / e.x2;
        break;
    }
    return t;
}

int main()
{
    ifstream in("evaluare.in");
    ofstream out("evaluare.out");

    char input[100002];
    in >> input;
    int n = makeEdges(input);
    for (int i = 1; i <= n; i++)
        id[i] = i;
    qsort(id+1, n, sizeof(int), compare);
    for (int i = 1; i < n; i++)
    {
        int t = compute(edges[id[i]]);
        edges[edges[id[i]].left].x2 = t;
        edges[edges[id[i]].left].right = edges[id[i]].right;
        edges[edges[id[i]].right].x1 = t;
        edges[edges[id[i]].right].left = edges[id[i]].left;
    }
    out << compute(edges[id[n]]) << '\n';

    return 0;
}