Pagini recente » Cod sursa (job #2890838) | Cod sursa (job #880518) | Cod sursa (job #1512772) | Cod sursa (job #827151) | Cod sursa (job #1214246)
//varianta cu arbori, sursa mare (approx. 4kb) si tot felul de codificari
#include <fstream>
#include <cstring>
#include <vector>
#define MX 100005
using namespace std;
// -1=+, -2=-, -3=*, -4=/
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
int l;
char s[MX];
vector<char> inf; //infix si stack
vector<int> pof; //postfix si rezultatul final
struct nod
{
int info;
nod *left, *right;
}*prim;
vector<nod*> rez;
void citire()
{
fin>>s;
l = strlen(s);
}
int numar(int &i)
{
int nr=0;
while(s[i]>='0' && s[i]<='9')
{
nr = nr*10 + s[i] - '0';
i++;
}
i--;
return nr;
}
void infix_to_postfix()
{
int i;
char x;
for(i=0; i<l; i++)
{
if(s[i]=='*' || s[i]=='/')
{
inf.push_back(s[i]);
}
else
if(s[i]=='+' || s[i]=='-')
{
if(!inf.empty())
{
x = inf.back();
while(x=='*' || x=='/')
{
inf.pop_back();
//pof.push_back(x);
if(x == '*') pof.push_back(-3);
else pof.push_back(-4);
x = inf.back();
}
}
inf.push_back(s[i]);
}
else
if(s[i]=='(')
{
inf.push_back(s[i]);
}
else
if(s[i]==')')
{
x = inf.back();
while(x != '(')
{
inf.pop_back();
//pof.push_back(x);
if(x == '+') pof.push_back(-1);
if(x == '-') pof.push_back(-2);
if(x == '*') pof.push_back(-3);
if(x == '/') pof.push_back(-4);
x = inf.back();
}
inf.pop_back();
}
else
{
pof.push_back(numar(i));
}
/*fout<<i;
fout.flush();*/
}
while(!inf.empty())
{
//pof.push_back(inf.back());
x = inf.back();
if(x == '+') pof.push_back(-1);
if(x == '-') pof.push_back(-2);
if(x == '*') pof.push_back(-3);
if(x == '/') pof.push_back(-4);
inf.pop_back();
}
//fout<<pof[5];
}
void postfix_to_rez()
{
l = pof.size();
nod *p, *op1, *op2;
vector<int>::iterator it;
for(it=pof.begin(); it!=pof.end(); it++)
{
if(*it >= 0)
{
p = new nod;
p->info = *it;
p->left = NULL;
p->right = NULL;
rez.push_back(p);
}
else
{
op1 = rez.back(); rez.pop_back();
op2 = rez.back(); rez.pop_back();
p = new nod;
p->info = *it;
p->left = op2;
p->right = op1;
rez.push_back(p);
}
}
//prim = p;
}
void SDR(nod* p)
{
if(p != NULL)
{
SDR(p->left);
SDR(p->right);
//fout<<p->info<<' ';
delete p;
}
}
int suma(nod *p)
{
if(p == NULL) return 0;
else
{
if(p->info >= 0) return p->info;
else
{
switch(p->info)
{
case -1: return( suma(p->left) + suma(p->right) ); break;
case -2: return( suma(p->left) - suma(p->right) ); break;
case -3: return( suma(p->left) * suma(p->right) ); break;
case -4: return( suma(p->left) / suma(p->right) ); break;
}
}
}
}
int main()
{
citire();
infix_to_postfix(); //inf e gol, pof are postfix
postfix_to_rez();
prim = rez[0];
rez.clear();
pof.clear();
fout<<suma(prim);
SDR(prim);
fin.close(); fout.close();
return 0;
}