Cod sursa(job #1637573)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 7 martie 2016 18:06:50
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.77 kb
#include <fstream>
#include <stack>
#include <cstring>
#define pl 1000000001
#define mi 1000000002
#define in 1000000003
#define im 1000000004
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
char s[100005];
int a[100005],k;
inline int prior(char ch)
{
if (ch=='+' || ch=='-') return 0;
if (ch=='*' || ch=='/') return 1;
if (ch=='(') return -1;
}
void polishform()
{
int i,nr;
char ch;
stack <char> st;
for (i=0;s[i];++i)
  {
  if (isdigit(s[i])) {
                     nr=0;
                     while (isdigit(s[i])) nr=nr*10+(s[i++]-'0');
                     i--;
                     a[k++]=nr;
                     }
  if (s[i]=='(') st.push('(');
  if (s[i]==')') {
                 while (st.top()!='(') {
                                        ch=st.top();
                                        if (ch=='+') a[k++]=pl;
                                        if (ch=='-') a[k++]=mi;
                                        if (ch=='*') a[k++]=in;
                                        if (ch=='/') a[k++]=im;
                                        st.pop();
                                       }
                  st.pop();
                 }
  if (strchr("+-*/",s[i])) if (st.empty()) st.push(s[i]);
                              else if (st.top()=='(') st.push(s[i]);
                                   else {while(!st.empty() && prior(st.top())>=prior(s[i]))
                                                   {
                                                   ch=st.top();
                                                   if (ch=='+') a[k++]=pl;
                                                   if (ch=='-') a[k++]=mi;
                                                   if (ch=='*') a[k++]=in;
                                                   if (ch=='/') a[k++]=im;
                                                   st.pop();
                                                   }
                                               st.push(s[i]);
                                              }
  }
while (!st.empty()) {
                    ch=st.top();
                    if (ch=='+') a[k++]=pl;
                    if (ch=='-') a[k++]=mi;
                    if (ch=='*') a[k++]=in;
                    if (ch=='/') a[k++]=im;
                    st.pop();
                    }
}
int eval()
{
stack <int> st;
for (int i=0;i<k;i++)
if (a[i]<pl) st.push(a[i]);
    else {
         int x=st.top();st.pop();
         int y=st.top();st.pop();
         if (a[i]==pl) st.push(x+y);
         if (a[i]==mi) st.push(y-x);
         if (a[i]==in) st.push(x*y);
         if (a[i]==im && x) st.push(y/x);
         }
return st.top();
}
int main()
{
fin.getline(s,100004);
polishform();
fout<<eval();
}