Cod sursa(job #341746)

Utilizator AstronothingIulia Comsa Astronothing Data 19 august 2009 14:05:45
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
#include <fstream>
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

bool isoperand(string s)
{
    for(int i=0;i<s.size();++i)
        if(s[i]>'9' || s[i]<'0')
            return 0;
    return 1;
}
bool isoperator(string s)
{
    string ops("+-/*");
    return (ops.find(s[0])!=string::npos);
}
long long toInt(string s)
{
    int res;
    stringstream ss;
    ss<<s;
    ss>>res;
    return res;
}
string goahead(string& s)
{
    int i=0;
    string res;
    while(i<s.size() && s[i]>='0' && s[i]<='9') i++;
    if(!i) i = 1;
    if(i<s.size()) { res = s.substr(0,i); s = s.substr(i); }
    else { res = s; s = ""; }
    return res;

    return s;
}
string c2s(char c)
{
    string res = "";
    res += c;
    return res;
}
int priority(char c)
{
    switch(c)
    {
        case '+': return 2;
        case '-': return 2;
        case '/': return 1;
        case '*': return 1;
        case '(': return 3;
    }
}

queue<string> toPostfix(string s)
{
    queue<string> pform;
    stack<char> ops;
    string strcrt = goahead(s);
    char c;
    do
    {
        c = 'x';
        if(isoperand(strcrt))
            pform.push(strcrt);
        else if(isoperator(strcrt))
        {
            if(ops.empty()) ops.push(strcrt[0]);
            else
            {
                while(!ops.empty() && priority(ops.top())<=priority(strcrt[0]))
                {
                    c = ops.top();
                    ops.pop();
                    pform.push(c2s(c));
                }
                ops.push(strcrt[0]);
            }
        }
        else if(strcrt[0] == '(') ops.push(strcrt[0]);
        else if(strcrt[0] == ')')
        {
            while(!ops.empty() && c!='(')
            {
                c = ops.top();
                ops.pop();
                if(c!='(')
                    pform.push(c2s(c));
            }

        }
        strcrt = goahead(s);
    } while(strcrt.size());
    while(!ops.empty()) { c = ops.top(); ops.pop(); pform.push(c2s(c)); }
    return pform;
}
long long minieval(char op,long long a,long long b)
{
    switch(op)
    {
        case '+': return a+b;
        case '-': return b-a;
        case '/': return b/a;
        case '*': return a*b;
    }
}

long long eval(queue<string> p)
{
    stack<int> numbers;
    while(!p.empty())
    {
        string s = p.front();
        p.pop();
        if(isoperand(s)) numbers.push(toInt(s));
        else
        {
            long long nr1 = numbers.top();
            numbers.pop();
            long long nr2 = numbers.top();
            numbers.pop();
            numbers.push(minieval(s[0],nr1,nr2));
        }
    }
    if(numbers.size()!=1) cout<<"wtf";
    return numbers.top();
}

int main()
{
    ifstream f("evaluare.in");
    ofstream f2("evaluare.out");
    string s;
    f>>s;
    queue<string> pform = toPostfix(s);
    f2<<eval(pform);

    return 0;
}