Cod sursa(job #527169)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 30 ianuarie 2011 20:15:12
Problema Evaluarea unei expresii Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.69 kb
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#define N 100001
typedef struct stack
{char st[N];
long sp;};
typedef struct stiva
{long v[N],n;};
char inf[N],postf[N];
long i,j;

void add(stiva &s,long nr)
{s.v[++s.n]=nr;}

long del(stiva &s)
{return s.v[s.n--];}

void push(stack &s,char ch)
{s.st[++s.sp]=ch;}

char pop(stack &s)
{return s.st[s.sp--];}

char top(stack s)
{return s.st[s.sp];}

long eval(char postf[N])
{stiva q;
char ch;
long i=0,nr,t1,t2;
q.n=0;
while(i<strlen(postf))
       {while(postf[i]==' ')
             i++;
       ch=postf[i];
       if(ch>='0'&&ch<='9')
             {nr=0;
             while(postf[i]>='0'&&postf[i]<='9')
                    {nr=nr*10+(postf[i]-'0');
                    i++;}
             add(q,nr);}
       else
             {if(ch=='+')
                    {t2=del(q);
                    t1=del(q);
                    add(q,t1+t2);}
             else
                    if(ch=='-')
                            {t2=del(q);
                            t1=del(q);
                            add(q,t1-t2);}
                    else
                            if(ch=='*')
                                    {t2=del(q);
                                    t1=del(q);
                                    add(q,t1*t2);}
                            else
                                    if(ch=='/')
                                            {t2=del(q);
                                            t1=del(q);
                                            add(q,t1/t2);}
             i++;}}
return del(q);}

int pri(char ch)
{int k,n=5,pr[]={0,1,1,2,2};
char v[]={'(','+','-','*','/'};
for(k=0;k<n;k++)
if(ch==v[k])
       return pr[k];}

void topostf(char in[N],char out[N])
{stack s;
char ch;
s.sp=0;
long i=0,j=0,r;
while(i<strlen(in))
       {ch=in[i++];
       if(ch>='0'&&ch<='9')
              out[j++]=ch;
       else
              {out[j++]=' ';
              if(ch=='(') 
                      push(s,ch);
              else
                      if(ch==')')
                           {while(s.sp!=0&&((r=pop(s))!='('))
                                 {out[j++]=r;
                                 out[j++]=' ';}}
                      else
                           {while(s.sp!=0&&pri(ch)<=pri(top(s)))
                                 {out[j++]=pop(s);
                                 out[j++]=' ';}
                           push(s,ch);}}}
while(s.sp!=0)
      {out[j++]=pop(s);
      out[j++]=' ';}
out[j]='\0';}

int main()
{ifstream f1("evaluare.in");
ofstream f2("evaluare.out");
f1>>inf;
topostf(inf,postf);
f2<<eval(postf);
f1.close();
f2.close();
return 0;}