Cod sursa(job #1759619)

Utilizator CatalinOlaruCatalin Olaru CatalinOlaru Data 19 septembrie 2016 17:16:59
Problema Evaluarea unei expresii Scor 80
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<map>
#include<sstream>
using namespace std;
map<string,int> dic;
char expr[100005];
string list[100005];
stack<string> postfix;
stack<string> stiva;
int nrs;
bool token(char c)
{
    if(c=='+' || c=='*' || c=='(' || c==')' || c=='-' || c=='/')
        return true;
    return false;
}
/*void convertToList(char * str)
{
    for(int i=0;i<len;i++)
    {
        string s="";
        if(token(str[i]))
        {
            s+=str[i];
            list[nrs++]=s;
        }
        else{
            s+=str[i++];
            while(!token(str[i]) && i<len)
            {
                s+=str[i++];
            }
            i--;
            list[nrs++]=s;
        }
    }
}
*/
void myPush(string curent)
{
    stack<string> st;
    st=stiva;
    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
    {
        if(curent!="(") {
            string el = " ";
            if (!stiva.empty())
                el = stiva.top();
            while (!stiva.empty() && dic[el] >= dic[curent]) {
                postfix.push(el);
                stiva.pop();
                if (!stiva.empty())
                    el = stiva.top();
            }
        }
        stiva.push(curent);

    }
}

void transform()
{
    int i=0;
    int len=strlen(expr);

    while(i<len)
    {
        string s="";
        if(token(expr[i]))
        {
            s+=expr[i];
            list[nrs++]=s;
        }
        else{
            s+=expr[i++];
            while(!token(expr[i]) && i<len)
            {
                s+=expr[i++];
            }
            i--;
            list[nrs++]=s;
        }
        i++;
        string el=s;
        if(token(el.c_str()[0]))
        {
            myPush(el);
        }
        else postfix.push(el);
    }
    while(!stiva.empty())
    {
        postfix.push(stiva.top());
        stiva.pop();
    }
}
int evaluate()
{
    string el=postfix.top();postfix.pop();
    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;
        }
    }
    return atoi(el.c_str());
}
int main()
{
    dic["+"]=2;dic["-"]=2;dic["*"]=3;dic["/"]=3;dic["("]=1;dic[")"]=1;
    fstream f,g;
    f.open("evaluare.in",ios::in);
    g.open("evaluare.out",ios::out);
    f>>expr;
    //convertToList(expr);
    transform();

    int n=evaluate();
    g<<n<<endl;
}