Pagini recente » Cod sursa (job #1616637) | Cod sursa (job #1522549) | Istoria paginii utilizator/lumi_nst | Istoria paginii runda/simulare_oni_10_z1_2k15/clasament | Cod sursa (job #1464232)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
using namespace std;
ifstream f("evaluare.in");
ofstream g("evaluare.out");
int N,rez,dimpolpost;
int prio[50];
char sir[100010];
struct pol {
int nr;
char c;
bool e_nr;
};
pol polpost[100010]; // polpost[i]=fiecare element al formei poloneze postfixate. daca e_nr=true => avem un operand else avem un operator
struct stiva { // stiva alocata dinamic
char val;
stiva* next=NULL;
};
stiva* stiv;
struct nod {
int nr;
char c;
bool e_nr;
nod* right=NULL;
nod* left=NULL;
};
struct stivanod_struct { // stiva alocata dinamic
nod val;
stivanod_struct* next=NULL;
};
stivanod_struct* stivanod;
bool gol();
char top();
void pop();
void push(char);
bool golnod();
nod topnod();
void popnod();
void pushnod(nod);
void determina_nr(int&,int&);
void parcurgere(nod*);
int main()
{
f>>sir;
N=strlen(sir);
prio['(']=1;
prio[')']=2;
prio['+']=prio['-']=3;
prio['*']=prio['/']=4;
stiv=new stiva;
for (int i=0;i<N;++i) {
if (sir[i]>=48 && sir[i]<=57) {
int nr=0;
determina_nr(nr,i);
polpost[++dimpolpost].nr=nr;
polpost[dimpolpost].e_nr=true;
--i;
}
else if (sir[i]=='(') {
push('(');
}
else if (sir[i]==')') {
while (top()!='(') {
polpost[++dimpolpost].c=top();
polpost[dimpolpost].e_nr=false;
pop();
}
pop();
}
else {
while (!gol() && prio[top()]>=prio[sir[i]]) {
polpost[++dimpolpost].c=top();
polpost[dimpolpost].e_nr=false;
pop();
}
push(sir[i]);
}
}
while (!gol()) {
polpost[++dimpolpost].c=top();
polpost[dimpolpost].e_nr=false;
pop();
}
stivanod=new stivanod_struct;
FOR (i,1,dimpolpost) { // se construieste arborele
if (polpost[i].e_nr) {
nod a;
a.e_nr=true;
a.nr=polpost[i].nr;
pushnod(a);
}
else {
nod* nod1=new nod;
*nod1=topnod();
popnod();
nod* nod2=new nod;
*nod2=topnod();
popnod();
nod a;
a.e_nr=false;
a.c=polpost[i].c;
a.left=nod2;
a.right=nod1;
pushnod(a);
}
}
nod* a=new nod;
*a=topnod(); // a=pointer spre radacina arborelui
parcurgere(a);
g<<a->nr;
f.close();g.close();
return 0;
}
bool gol() {
if (stiv->next==NULL) {
return true;
}
return false;
}
char top() {
return stiv->val;
}
void pop() {
stiva* p=stiv;
stiv=stiv->next;
delete p;
}
void push(char x) {
stiva* p=new stiva;
p->val=x;
p->next=stiv;
stiv=p;
}
bool golnod() {
if (stivanod->next==NULL) {
return true;
}
return false;
}
nod topnod(){
return stivanod->val;
}
void popnod(){
stivanod_struct* p=stivanod;
stivanod=stivanod->next;
delete p;
}
void pushnod(nod x) {
stivanod_struct* p=new stivanod_struct;
p->val=x;
p->next=stivanod;
stivanod=p;
}
void determina_nr(int& nr,int& i) {
while (sir[i]>=48 && sir[i]<=57) {
nr=nr*10+sir[i]-48;
++i;
}
}
void parcurgere(nod* x) {
nod* l=x->left;
nod* r=x->right;
if (!l->e_nr) {
parcurgere(l);
}
if (!r->e_nr) {
parcurgere(r);
}
x->e_nr=true;
switch (x->c) {
case ('+'): {
x->nr=l->nr+r->nr;
break;
}
case ('-'): {
x->nr=l->nr-r->nr;
break;
}
case ('*'): {
x->nr=l->nr*r->nr;
break;
}
case ('/'): {
x->nr=l->nr/r->nr;
break;
}
}
}