Cod sursa(job #1276286)

Utilizator cdascaluDascalu Cristian cdascalu Data 26 noiembrie 2014 09:57:09
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.26 kb
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <stack>
#include <algorithm>
#define Nmax 300001
using namespace std;

struct Node
{
    int val;
    bool is_op;
    Node *left, *right;
};
int priority(char x)
{
    switch (x)
    {
        case '+' : return 1;
        case '-' : return 1;
        case '*' : return 2;
        case '/' : return 2;
        default: return 3;
    }
}
char* getPostfix(char* s)
{
    int sz = strlen(s), cnt = 0;
    char res[Nmax];
    bool is_number = false;

    stack<char> S;
    for(int i=0;i<sz;++i)
    {
        if(s[i] == '\n')
            continue;
        if(s[i] >= '0' && s[i] <= '9')
        {
            res[cnt++] = s[i];
            is_number = true;
        } else {

            if(is_number)
            {
                res[cnt++] = ' ';
                is_number = false;
            }

            if(s[i] == '(')
            {
                S.push('(');
                continue;
            }

            if(s[i] == ')')
            {
                while(S.top() != '(')
                {
                    res[cnt++] = S.top();
                    S.pop();
                }
                S.pop();

                continue;
            }

            while(!S.empty() && S.top() != '(' && priority(S.top()) >= priority(s[i]))
            {
                res[cnt++] = S.top();
                S.pop();
            }
            S.push(s[i]);
        }
    }

    while(!S.empty())
    {
        res[cnt++] = S.top();
        S.pop();
    }

    return res;
}

Node* createExpTree(char* postfix)
{
    int sz = strlen(postfix), nr = 0;
    bool is_number = false;

    stack<Node*> S;
    for(int i=0;i<sz;++i)
    {
        if(postfix[i] >= '0' && postfix[i] <= '9')
        {
            nr = nr * 10 + (postfix[i] - '0');
            is_number = true;
        }
        else
        {
            if(is_number)
            {
                Node*p = new Node;
                p->val = nr;
                p->is_op = false;
                p->left = NULL;
                p->right = NULL;
                S.push(p);

                is_number = false;
                nr = 0;
            }

            if(postfix[i] == ' ')
                continue;

            Node*p = new Node;
            p->val = postfix[i];
            p->is_op = true;

            p->right = S.top(); S.pop();
            p->left = S.top(); S.pop();
            S.push(p);
        }
    }

    return S.top();
}

void postorder(Node *p)
{
    if(p->left != NULL)
        postorder(p->left);

    if(p->right != NULL)
        postorder(p->right);

    if(p->is_op)
        cout<<char(p->val)<<" ";
    else
        cout<<p->val<<" ";
}

int evaluate(Node *p)
{
    if(p->is_op)
    {
        int left = evaluate(p->left);
        int right = evaluate(p->right);
        switch (p->val)
        {
            case '+' : return left + right;
            case '-' : return left - right;
            case '*' : return left * right;
            case '/' : return left / right;
        }
    }
    else return p->val;
}
int main()
{
    char buf[Nmax];
    ifstream f("evaluare.in");
    f.getline(buf, Nmax);
    f.close();

    Node *R = createExpTree(getPostfix(buf));
    ofstream g("evaluare.out");
    g<<evaluate(R);
    g.close();
    return 0;
}