Cod sursa(job #1759558)

Utilizator CatalinOlaruCatalin Olaru CatalinOlaru Data 19 septembrie 2016 15:11:38
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.85 kb
#include<stdlib.h>
#include<fstream>
#include<iostream>
#include<stack>
#include<string.h>
#include<queue>
#include<sstream>
using namespace std;
char expr[100005];
queue<string> list;
stack<string> postfix;
stack<string> stiva;
bool token(char c)
{
    if(c=='+' || c=='*' || c=='(' || c==')' || c=='-' || c=='/')
        return true;
    return false;
}
void convertToList(char * str)
{
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        string s="";
        if(token(str[i]))
        {
            s+=str[i];
            list.push(s);
        }
        else{
            s+=str[i++];
            while(!token(str[i]) && i<len)
            {
                s+=str[i++];
            }
            i--;
            list.push(s);
        };
    }
}
int priority(string q)
{
    char c=q.c_str()[0];
    int p=0;
    if(c=='+')
        p=2;
    else if(c=='-')
        p=2;
    else if(c=='*')
        p=3;
    else if(c=='/')
        p=3;
    else if(c=='(')
        p=1;
    else if(c==')')
        p=1;
    return p;
}
void myPush(string curent)
{
    //cout<<"intra "<<curent<<endl;
    if(curent==")")
    {
        int cont=-1;
        while(cont<0)
        {
            string el=stiva.top();stiva.pop();
            if(el=="(")
                cont++;
            else if(el==")")
                cont--;
            else
                postfix.push(el);
        }
    }
    else
    {
        string el=" ";
        if(!stiva.empty())
            el=stiva.top();
        while(!stiva.empty() && priority(el)>priority(curent))
        {
            postfix.push(el);stiva.pop();
            if(!stiva.empty())
            el=stiva.top();
        }

        stiva.push(curent);
      //  cout<<"Face ok"<<endl;
    }
}

void transform()
{
    while(!list.empty())
    {

        string el=list.front();list.pop();
        if(token(el.c_str()[0]))
        {
            myPush(el);
        }
        else postfix.push(el);
    //    cout<<"element "<<el<<endl;
    }
    while(!stiva.empty())
    {
        postfix.push(stiva.top());
        stiva.pop();
    }
}
int evaluate()
{
    string el=postfix.top();postfix.pop();
    //cout<<"element "<<el<<endl;
    if(token(el.c_str()[0]))
    {
        int x = evaluate();
        int y = evaluate();
        if(el=="/")
        {
            return y/x;
        }
        else if(el=="*")
        {
            return y*x;
        }
        else if(el=="+")
        {
            return y+x;
        }
        else if(el=="-")
        {
            return y-x;
        }
    }
    else
        return atoi(el.c_str());
}
int main()
{
    fstream f,g;
    f.open("evaluare.in",ios::in);
    g.open("evaluare.out",ios::out);
    f>>expr;
    //g<<expr<<endl;
    convertToList(expr);

    transform();
    int n=evaluate();
    g<<n<<endl;
//    while(!postfix.empty())
//    {
//        g<<postfix.front()<<"|";
//        postfix.pop();
//    }
}