Cod sursa(job #1636916)

Utilizator mateialexandru25Matei Alexandru mateialexandru25 Data 7 martie 2016 13:29:56
Problema Evaluarea unei expresii Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <stack>
#include <cstring>
#include <fstream>
using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

char s[100001]; //expresia initiala
char polon[100001]; //expresia in forma poloneaza postfixata
stack <char> O; //oper - mem. temporar operatorii
char op[]="+-*/";
int v[100001];
int n;

inline int P(char c)
{ if(c=='+' || c=='-') return 1;
  else return 2;
}

void Poloneza()
{  int i,nr;
   n=0; //lg. sirului polon
   for(i=0;s[i]!=0;i++)
   { if(s[i]>='0'&& s[i]<='9')
        {  nr=0;
           while(s[i]>='0' && s[i]<='9') {nr=nr*10+s[i]-'0'; i++;}
           polon[n]='a'; //este operand
           v[n++]=nr;
           i--;
           continue;
        }
     if(s[i]=='(') O.push(s[i]);
     if(s[i]==')') {while(O.top()!='(')
                        {polon[n++]=O.top(); O.pop();}
                    O.pop(); //pentru paranteza deschisa
                   }
     if(strchr(op,s[i]))
        if(O.empty()) O.push(s[i]);
        else if(O.top()=='(') O.push(s[i]);
             else { while(!O.empty() && O.top()!='(' && P(O.top())>P(s[i]))
                          {polon[n++]=O.top(); O.pop();}
                    O.push(s[i]);
                  }
   }
   while(!O.empty()) {polon[n++]=O.top(); O.pop();}
   polon[n]=0;
}

void Evaluare()
{   int i,k,val;
    while(n>1)
    { i=0;
      while(polon[i]=='a') i++;
      if(polon[i]=='+') val=v[i-2]+v[i-1];
      if(polon[i]=='-') val=v[i-2]-v[i-1];
      if(polon[i]=='*') val=v[i-2]*v[i-1];
      if(polon[i]=='/') if(v[i-1]!=0) val=v[i-2]/v[i-1];
                        else val=0;
      v[i-2]=val;
      strcpy(polon+i-1,polon+i+1);
      for(k=i-1;k<n;k++) v[k]=v[k+2];
      n=n-2;
    }
    fout<<v[0];
}

int main()
{
    fin>>s;
    Poloneza();
    //fout<<polon<<"\n";
    //for(int i=0;i<n;i++) fout<<v[i]<<" ";
    //fout<<"\n";
    Evaluare();
    return 0;
}