Pagini recente » Cod sursa (job #850749) | Cod sursa (job #1888952) | Cod sursa (job #302491) | Cod sursa (job #122562) | Cod sursa (job #758536)
Cod sursa(job #758536)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <stack>
#include <string.h>
#define NMAX 200000
using namespace std;
typedef struct node{
int val;
node *left,*right;
}node;
char s[NMAX];
char s2[NMAX];
int priority(char c)
{
if (c=='+'|| c=='-')
return 2;
if (c=='*' ||c=='/')
return 1;
/* if (c=='(' || c==')')
return 0;*/
return 10;
}
void transform(char *s,char *s2)
{
int i,p;
i = 0;
p = 0;
int k = strlen(s);
stack<char> stiva;
stiva.push('x');
while (i<k)
{
while (s[i]==' ' || s[i]=='\t') i++;
if ( s[i]>='0' && s[i]<='9')
{
while (s[i]>='0' && s[i]<='9')
{
s2[p] = s[i];
i++;
p++;
}
s2[p]=' ';p++;
}
if (s[i]=='(')
{
stiva.push(s[i]);
i++;
}
if (s[i]==')')
{
char c = stiva.top();stiva.pop();
while (c!='(')
{
s2[p] = c;
p++;
s2[p]= ' ';
p++;
c = stiva.top();stiva.pop();
}
i++;
}
if (s[i]=='+' || s[i] =='*' || s[i] == '-' || s[i]=='/')
{
if (stiva.top()=='x')
stiva.push(s[i]);
else {
char c = stiva.top();stiva.pop();
while (priority(c)<=priority(s[i]))
{
s2[p] = c;
c = stiva.top();stiva.pop();
p++;
s2[p]=' ';
p++;
}
stiva.push(c);
stiva.push(s[i]);
}
i++;
}
}
while (stiva.top()!='x')
{
s2[p] = stiva.top();
stiva.pop();
if (s2[p]!='('){
p++;
s2[p] =' ';
p++;
}
}
s2[p]='\0';
}
node *totree(char *s)
{
stack<node*> stiva;
stiva.push(NULL);
char *i = s;
while (i<s+strlen(s)*sizeof(char))
{
if (*i==' ')
i++;
if (*i>='0' && *i<='9')
{
node *a = new node;
a->val = *i-'0';
i++;
while (*i>='0' && *i<='9')
{
a->val = a->val*10+(*i-'0');
i++;
}
a->left = NULL;
a->right = NULL;
stiva.push(a);
}
else if (*i=='+' || *i =='*' || *i == '-' || *i=='/')
{
node *a = stiva.top();stiva.pop();
node *b = stiva.top();stiva.pop();
node *c = new node;
c->val = *i;
c->left = a;
c->right = b;
stiva.push(c);
i++;
}
else i++;
}
return stiva.top();
}
int eval(node *T)
{
if (T->right!=0 &&T->left!=NULL)
{
int k1 = eval(T->right);
int k2 = eval(T->left);
switch(T->val)
{
case '+':{
return k1+k2;
}
break;
case '-':{
return k1-k2;
}
break;
case '*':{
return k1*k2;
}
break;
case '/':{
return k1/k2;
}
break;
default:
return 0;
}
}
else
return T->val;
}
int main()
{
ifstream f("evaluare.in",ios::in);
f>>s;
node *T;
strcpy(s2,s);
transform(s,s2);
//cout<<s2<<endl;
T =totree(s2);
int rez = eval(T);
f.close();
ofstream g("evaluare.out",ios::out);
g<<rez<<endl;
g.close();
return 0;
}