Cod sursa(job #1461210)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 15 iulie 2015 01:56:02
Problema Evaluarea unei expresii Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 4.82 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct NodStiva{
    char opr;
    struct NodStiva* next;
}NodStiva;
typedef struct NodStivaInt{
    int val;
    struct NodStivaInt* next;
}NodStivaInt;
typedef struct NodCoada{
    int opd;
    char opr; 
    struct NodCoada* next;
}NodCoada;

NodStiva* push(NodStiva* vf,char c){
    NodStiva* nou=( NodStiva*)malloc(sizeof(NodStiva));
    nou->opr=c;
    nou->next=vf;
    return nou;
}
NodStiva* pop(NodStiva* vf,char *c){
    if(vf){
        *c = vf->opr;
        NodStiva * t=vf;
        vf = vf->next;
        free(t);
        
    }
    
    return vf; 
}
NodStivaInt* push_int(NodStivaInt* vf,int c){
    NodStivaInt* nou=( NodStivaInt*)malloc(sizeof(NodStivaInt));
    nou->val=c;
    nou->next=vf;
    return nou;
}
NodStivaInt* pop_int(NodStivaInt* vf,int *c){
    if(vf){
        *c = vf->val;
        NodStivaInt * t=vf;
        vf = vf->next;
        free(t);
        
    }
    
    return vf; 
}
void push_c(NodCoada ** front ,NodCoada ** rear , int v , char o){
    if( *front == NULL){
        *front = (NodCoada*)malloc(sizeof(NodCoada));
        (*front)->opd = v ;
        (*front)->opr = o ;
        (*rear) = *front ;
        (*front)->next = NULL ;
        return;
    }
    NodCoada * nou = (NodCoada*)malloc(sizeof(NodCoada));
    nou->opd = v ;
    nou->opr = o ;
    nou->next = NULL ;
    (*rear)->next = nou ;
    *rear = nou ;


}
int prioritate(char c){
    switch(c){
        case '(':
            return 1;
        case ')':
            return 2;
        case '+':
        case '-':
            return 3;
        case '*':
        case '/':
            return 4;
        default:
            return 5;
    } 
}
NodStiva * postfix(char  crt_c , int crt_i , NodCoada ** front , NodCoada ** rear , NodStiva * stack  ){
    char o ;
    if(crt_c == 0){
        push_c(front,rear,crt_i,crt_c);
    }
    else{ // acum analizam operatorii
            if(crt_c == '('){
                stack = push(stack,crt_c);
                return stack;
            }
            else{
                    if(crt_c == ')'){
                        char o ;
                        stack=pop(stack,&o);
                        while(o != '('){
                          push_c(front,rear,0,o);  
                          
                          stack=pop(stack,&o);
                        }
                        return stack;
                    }

            }
    }
    if(prioritate(crt_c) < 5){
        if(stack){
            while(stack && prioritate(stack->opr) > prioritate(crt_c)){
                stack=pop(stack,&o);
                push_c(front,rear,0,o);
            }
        }
        stack=push(stack,crt_c);
    }
    
    return stack ;
}        


void parse(char * expresie,int dimensiune, NodCoada ** front , NodCoada ** rear , NodStiva * stack){
    int i ;
    i = 0 ;
    int numar ;
    while(i < dimensiune){
        if(expresie[i] == '(' || expresie[i] == ')' || expresie[i] == '+' || expresie[i] == '-' || expresie[i] == '*' || expresie[i] == '/'){
            stack = postfix(expresie[i],0,front,rear,stack);
            i++;
            continue ;
        }
        numar = 0;
      
        
        while('0' <= expresie[i] && expresie[i] <= '9'){
             
            numar = numar * 10 + (int)expresie[i] - 48;
            i++;
        }
         stack = postfix(0,numar,front,rear,stack);
      

    }
    char o ;
    while(stack){
        stack=pop(stack,&o);
        push_c(front,rear,0,o);
    }
    
}
int calcul(NodCoada * front ,NodCoada  * rear  ){
    NodStivaInt * stack;
    NodCoada * cursor = front ;
    int rez;
    int opd1 , opd2 ;
    while(cursor != NULL){
        if(cursor->opr == 0){
            stack = push_int(stack,cursor->opd);
           
            }
        else{
         
            char opr = cursor->opr ;
            stack = pop_int(stack,&opd2);
            stack = pop_int(stack,&opd1);
            switch(opr){
                case '+':
                rez=opd1+opd2;
                break;
                case '-':
                rez=opd1-opd2;
                break;
                case '*':
                rez=opd1*opd2;
                break;
                case '/':

                rez=opd1/opd2;
              
                break;
            
            }
            stack = push_int(stack,rez);
            
        }
        cursor = cursor->next;
    }    
    return stack->val;
}
int main(void){
    FILE * in = fopen("evaluare.in","r");
    FILE * out = fopen("evaluare.out","w");
    char * expresie =(char*)malloc(100002*sizeof(char));
    fgets(expresie, 100001, in);
    NodCoada * front = NULL , * rear = NULL;
    NodStiva * stack = NULL;
    int dimensiune = strlen(expresie) - 1 ;
    parse(expresie,dimensiune,&front,&rear,stack);
    fprintf(out,"%d\n",calcul(front,rear) );
    fclose(in);
    fclose(out);
    return 0 ;
}