Cod sursa(job #344423)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 29 august 2009 23:49:40
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include<stdio.h>
#include<string.h>
int prior[300];
char s[100010];
char semn[100010];
int stack[100010];
int postfix[100010];
int l;
int i;
int p;
int top;
int Sign(char q)
{
    if (q == '+' || q == '-' || q == '*' || q == '/') return 1;
    return 0;
}
void Init()
{
    prior['*']= 2;
    prior['/']= 2;
    prior['+']= 1;
    prior['-']= 1;

}
int Construct()
{
    int i = 0;
     while (i < l)
    {
        if (s[i] == '(')
         stack[++top] = '(';
         else
        if (s[i] == ')')
         {
             while (stack[top] != '(')
              {
                  postfix[++postfix[0]] = stack[top];
                  if  (Sign(stack[top])) semn[postfix[0]] = 1;
                  top--;
              }
              top--;
         }
         else
         if (s[i] >= '0' && s[i] <= '9')
         {
             p = 0;
         while (s[i] >= '0' && s[i] <= '9')
          {
              p = p * 10 + s[i] - '0';
              i++;
          }
          postfix[++postfix[0]] = p;
          i--;
         }
         else
          if (Sign(s[i]))
           {
               while (prior[s[i]] <= prior[stack[top]])
                 {
                     postfix[++postfix[0]] = stack[top];
                     if  (Sign(stack[top])) semn[postfix[0]] = 1;
                     top--;
                 }
              //if  (Sign(stack[top])) semn[postfix[0]] = 1;
              stack[++top] = s[i];


           }
        i++;
    }
}
int main()
{
    freopen("evaluare.in","r",stdin);
    freopen("evaluare.out","w",stdout);

    scanf("%s",&s);


    l = strlen(s);
    for(int i = l; i >= 1; i--)
     s[i] = s[i-1];
    l = strlen(s);
    s[l] = ')';
    s[0] = '(';
    l = strlen(s);

    Init();
    Construct();

    for(;top;top--)
     stack[top] = 0;

    for(int i = 1; i <= postfix[0]; i++)
     {
         if (semn[i])
         {
         if (postfix[i] == '*')
          {
              stack[top-1] = stack[top-1] * stack[top];
              top--;
          }
          if (postfix[i] == '-')
          {
              stack[top-1] = stack[top-1] - stack[top];
              top--;
          }
          if (postfix[i] == '+')
          {
              stack[top-1] = stack[top-1] + stack[top];
              top--;
          }
          if (postfix[i] == '/')
          {
              stack[top-1] = stack[top-1] / stack[top];
              top--;
          }
         }
         else
         stack[++top] = postfix[i];

     }
     printf("%d",stack[1]);




    return 0;

}