Pagini recente » Cod sursa (job #2170618) | Cod sursa (job #882922) | Cod sursa (job #749381) | Cod sursa (job #1596551) | Cod sursa (job #1214236)
#include <cstdio>
using namespace std;
class Stack
{
private:
char s[50000];
int top;
public:
Stack(){};
Stack(int newTop):top(newTop){}
void pop() {--top;}
void push(char c)
{
++top;
this->s[top]=c;
}
bool isEmpty()
{
if(top>0) return 0;
return 1;
}
char Top() { return s[top]; }
void emptyStack() { top=0; }
};
typedef struct nod
{
nod *left,*right;
char op;
long val;
nod(long _val=0,char _op=' '):val(_val),op(_op){};
}NOD;
typedef struct{nod* v[100001];int top;} NodeStack;
bool isOperator(char c)
{
return (c=='+' || c=='-' || c=='*' || c=='/');
}
int priority(char c)
{
int pri=0;
if(c=='+' || c=='-') pri=1;
else if(c=='*' || c=='/') pri=2;
return pri;
}
NOD* pop(NodeStack &s) { NOD * n=s.v[s.top];--s.top; return n;}
void push(NodeStack &s,NOD *p) { s.v[++s.top]=p;}
long calculus(long a,long b,char c)
{
switch(c)
{
case '+': return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
}
}
long st[100001],m;
void evaluate(NOD *root)
{
long calc;
if(root!=NULL)
{
evaluate(root->left);
evaluate(root->right);
if(root->op==' ') st[++m]=root->val;
else
{
long a,b;
a=st[m];--m;
b=st[m];--m;
calc=calculus(b,a,root->op);
st[++m]=calc;
}
}
}
int main()
{
FILE *f,*g;
f=fopen("evaluare.in","r");
g=fopen("evaluare.out","w");
char s[100002],postfix[200002];
int i,length,neg,p=0;
long rez=0,nr=0;
length=fread(s,sizeof(char),100002,f);
Stack stack(0);
for(i=0;i<length;++i)
{
if(s[i]>='0' && s[i]<='9')
{
if(s[i-1]=='-' && i-2>=0 && s[i-2]=='(') postfix[p++]=s[i-1];
postfix[p++]=s[i];
while(s[i+1]>='0' && s[i+1]<='9')
{
++i;
postfix[p++]=s[i];
}
postfix[p++]=' ';
}
else if(s[i]=='(') stack.push(s[i]);
else if(s[i]==')')
{
while(stack.Top()!='(')
{
postfix[p++]=stack.Top();
postfix[p++]=' ';
stack.pop();
}
stack.pop();
}
else if(isOperator(s[i]) && !(s[i]=='-' && s[i+1]>='0' && s[i+1]<='9' && s[i-1]=='('))
{
if(stack.isEmpty())
{
stack.push(s[i]);
}
else
{
while(priority(stack.Top())>=priority(s[i]))
{
postfix[p++]=stack.Top();
postfix[p++]=' ';
stack.pop();
}
stack.push(s[i]);
}
}
}
while(!stack.isEmpty()) {postfix[p++]=stack.Top();postfix[p++]=' ';stack.pop();}
postfix[p]='\0';
NodeStack nstack;
nstack.top=0;
for(i=0;i<p;++i)
{
if(postfix[i]>='0' && postfix[i]<='9')
{
if(i-1>=0 && postfix[i-1]=='-') neg=1;
while(postfix[i]!=' ')
{
nr=nr*10+postfix[i]-'0';
++i;
}
if(neg==1) nr=nr*(-1);
NOD *newN=new nod;
newN->left=NULL;
newN->right=NULL;
newN->val=nr;
push(nstack,newN);
nr=0;
neg=0;
}
else if(isOperator(postfix[i]) &&!(postfix[i]=='-' && postfix[i+1]>='0' && postfix[i+1]<='9'))
{
NOD *op1,*op2;
op1=pop(nstack);
op2=pop(nstack);
NOD *newN=new nod;
newN->left=op2;
newN->right=op1;
newN->op=postfix[i];
push(nstack,newN);
}
}
NOD *root=pop(nstack);
stack.emptyStack();
evaluate(root);
fprintf(g,"%ld",st[m]);
fclose(f);
fclose(g);
return 0;
}