Cod sursa(job #758536)

Utilizator iris88Nagy Aliz iris88 Data 15 iunie 2012 22:11:44
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.26 kb
#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)
{
  int i,p;
  i = 0;
  p = 0;
  int k = strlen(s);
  stack<char> stiva;
  stiva.push('x');
  while (i<k)
  {
    while (s[i]==' ' || s[i]=='\t') i++;
    if ( s[i]>='0' && s[i]<='9')
    {
      while (s[i]>='0' && s[i]<='9')
      {
        s2[p] = s[i];
        i++;
        p++;
      }
      s2[p]=' ';p++;
    }
    if (s[i]=='(')
    {
      stiva.push(s[i]);
      i++;
    }
    if (s[i]==')')
    {
      char c = stiva.top();stiva.pop();
      while (c!='(')
      {
        s2[p] = c;
        p++;
        s2[p]= ' ';
        p++;
        c = stiva.top();stiva.pop();
      }
      i++;
    }
    if (s[i]=='+' || s[i] =='*' || s[i] == '-' || s[i]=='/')
    {
      if (stiva.top()=='x')
        stiva.push(s[i]);
      else {
        char c = stiva.top();stiva.pop();
        while (priority(c)<=priority(s[i]))
        {
          s2[p] = c;
          c = stiva.top();stiva.pop();
          p++;       
          s2[p]=' ';
          p++;
        }
        stiva.push(c);
        stiva.push(s[i]);
      }
      i++;
    }
  }
    while (stiva.top()!='x')
    {     
      s2[p] = stiva.top();
      stiva.pop();
      if (s2[p]!='('){
        p++;
        s2[p] =' ';
        p++;      
      }
    }
  
  s2[p]='\0';
}
node *totree(char *s)
{
  stack<node*> stiva;
  stiva.push(NULL);
  char *i = s;
  while (i<s+strlen(s)*sizeof(char))
  {
    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;
}