Pagini recente » Cod sursa (job #1573469) | Cod sursa (job #2414364) | Cod sursa (job #797239) | Cod sursa (job #1130386) | Cod sursa (job #758538)
Cod sursa(job #758538)
#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)
{
char *i,*p;
i = s;
p = s2;
int k = strlen(s);
stack<char> stiva;
stiva.push('x');
char *endi = s+strlen(s)*sizeof(char);
while (i<endi)
{
while (*i==' ' || *i=='\t') i++;
if ( *i>='0' && *i<='9')
{
while (*i>='0' && *i<='9')
{
*p = *i;
i++;
p++;
}
*p=' ';p++;
}
if (*i=='(')
{
stiva.push(*i);
i++;
}
if (*i==')')
{
char c = stiva.top();stiva.pop();
while (c!='(')
{
*p = c;
p++;
*p= ' ';
p++;
c = stiva.top();stiva.pop();
}
i++;
}
if (*i=='+' || *i =='*' || *i == '-' || *i=='/')
{
if (stiva.top()=='x')
stiva.push(*i);
else {
char c = stiva.top();stiva.pop();
while (priority(c)<=priority(*i))
{
*p = c;
c = stiva.top();stiva.pop();
p++;
*p=' ';
p++;
}
stiva.push(c);
stiva.push(*i);
}
i++;
}
}
while (stiva.top()!='x')
{
*p = stiva.top();
stiva.pop();
if (*p!='('){
p++;
*p =' ';
p++;
}
}
*p='\0';
}
node *totree(char *s)
{
stack<node*> stiva;
stiva.push(NULL);
char *i = s;
char *endi = s+strlen(s)*sizeof(char);
while (i<endi)
{
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;
}