Mai intai trebuie sa te autentifici.

Cod sursa(job #2016720)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 30 august 2017 10:19:46
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.98 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

FILE *in,*out;

const int nmax = 100000;

char c[nmax+3];

struct Symbol
{
    int tip;
    char semn;
    int val;
    int prior;
} v[1+nmax];

int n;

int prioritate(char x)
{
    if(x == '-' || x == '+')
        return 1;
    return 2;
}

void parsare()
{
    int i = 0, nr = 0, flag = 0;
    while(c[i] != '\0')
    {
        if(c[i] >= '0' && c[i] <= '9')  {
          if(flag == 0) {
            flag = 1;
            nr = c[i] - '0';
          } else {
             nr *= 10;
             nr += (c[i] - '0');
          }
        } else {
          if(flag == 1) {
            flag = 0;
            v[++n].tip = 4;
            v[n].val = nr;
          }
          if(c[i] == '-' || c[i] == '+' || c[i] == '*' || c[i] == '/')
          {
              v[++n].tip = 3;
              v[n].semn = c[i];
              v[n].prior = prioritate(c[i]);
          }
          else if(c[i] == '(')
              v[++n].tip = 1;
          else if(c[i] == ')')
              v[++n].tip = 2;
        }
        i ++;
    }
    if(flag == 1) {
      v[++n].tip = 4;
      v[n].val = nr;
    }
}

stack <int> opst;
vector <int> output;

//Ai + *  si vii cu un -
void converttopostfix() {
  for(int i = 1;i <= n;i ++) {
    if(v[i].tip == 3) {
      while(0 < opst.size() && v[opst.top()].tip != 1 && v[opst.top()].prior >= v[i].prior) {
        output.push_back(opst.top());
        opst.pop();
      }
      opst.push(i);
    } else if(v[i].tip == 1) {
      opst.push(i);
    } else if(v[i].tip == 2) {
      while(v[opst.top()].tip != 1) {
        output.push_back(opst.top());
        opst.pop();
      }
      opst.pop();
    } else if(v[i].tip == 4)
      output.push_back(i);
  }
  while(opst.size() > 0) {
     output.push_back(opst.top());
     opst.pop();
  }
}


int computepostfix() {
   if(output.size() == 1) {
     return  v[output[0]].val;
   } else {
     int eval[1 + nmax];
     int neval = 2;
     eval[1] = v[output[0]].val;
     eval[2] = v[output[1]].val;

     for(int i = 2; i < output.size(); i ++)  {
       if(v[output[i]].tip == 3) {
          if(v[output[i]].semn == '+') {
            eval[neval - 1] += eval[neval];
            neval--;
          } else if(v[output[i]].semn == '-') {
            eval[neval - 1] -= eval[neval];
            neval--;
          } else if(v[output[i]].semn == '*') {
            eval[neval - 1] *= eval[neval];
            neval--;
          } else if(v[output[i]].semn == '/') {
            eval[neval - 1] /= eval[neval];
            neval--;
          }
       } else {
          eval[++neval] = v[output[i]].val;
       }
     }
     return eval[1];
   }
}

int main()
{
    in = fopen("evaluare.in","r");
    out = fopen("evaluare.out","w");
    fgets(c,nmax+3,in);
    parsare();
    converttopostfix();
    fprintf(out,"%d",computepostfix());
    return 0;
}