Cod sursa(job #769048)

Utilizator mi5humihai draghici mi5hu Data 18 iulie 2012 09:32:33
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.98 kb
#include <stdio.h>
#include <fstream>
#include <stack>
#include <vector>
#include <queue>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define NMAX 100001

using namespace std;

char str[NMAX];
char IF[NMAX][11];
int IF_size;
queue<char*> PF;

void read_() {
     scanf("%s", str);
}

int eval(int a, int b, char op) {
     switch (op) {
         case '+':
              return (a + b);
         case '-':
              return (b - a);
         case '*':
              return (a * b);
         case '/':
              return (b / a); 
         default:
              return 0;              
     }
}

bool isOperator(char a) {
    if (a == '*' || a == '/' || a == '-' || a == '+') { 
              return true;
    }
    return false;
}

bool isParanthesis(char a) {
     if (a == '(' || a == ')') {
              return true;
     }
     return false;   
}

int priority(char c) {
    if (c == '*' || c == '/' || c == '%') {
       return 2;   
    } else if (c == '-' || c == '+') {
       return 1;       
    } 
    return 0;      
}

void infix2postfix() {
     stack<char*> myStack;
          
     int pozI = 0;       
     while (pozI < IF_size) {
         if (isdigit(IF[pozI][0])) {
             PF.push(IF[pozI++]);
         }      
         else if (IF[pozI][0] == '(') {
             myStack.push(IF[pozI++]);                
         }
         else if (IF[pozI][0] == ')') {
             char el[11];
             strcpy(el, myStack.top());
             myStack.pop();
             while (el[0] != '(') {
                  PF.push(strdup(el));
                  memset(el, 0, 11 * sizeof(char));
                  strcpy(el, myStack.top());
                  myStack.pop();    
                    
             }             
             pozI++;
         }
         else if (isOperator(IF[pozI][0])) {
            if (myStack.empty()) {
                myStack.push(IF[pozI++]);                     
            } else {
                while (!myStack.empty() && (priority(myStack.top()[0]) >= priority(IF[pozI][0]))) {
                     char el[11];
                     memset(el, 0, 11 * sizeof(char));
                     strcpy(el, myStack.top());
                     PF.push(strdup(el));
                     myStack.pop();      
                }       
                myStack.push(IF[pozI++]);
            }                     
         } else {
            pozI++;       
         }
     }        
     while (!myStack.empty()) {
         char el[11];
         strcpy(el, myStack.top());
         PF.push(strdup(el));
         myStack.pop();      
     }
}

int solve_() {
     stack<int> S;
     while (!PF.empty()) {
           char* el = strdup(PF.front());
           PF.pop();
           if (isdigit(el[0])) {
               int val = atoi(el);
               S.push(val);                    
           } else {
               int e1 = S.top();
               S.pop();
               int e2 = S.top();
               S.pop();
               int tmp = eval(e1, e2, el[0]);
               S.push(tmp);                                   
           }
                 
     }
     return S.top();       
} 

void getElements() {
     int i = 0, SL = strlen(str);
     while (i < SL) {         
         while (isOperator(str[i]) || isParanthesis(str[i])) {
             IF[IF_size++][0] = str[i]; 
             i++;                 
         } 
         if (isdigit(str[i])) {
             int p1 = i;
             while (isdigit(str[++i])) {}      
             strncpy(IF[IF_size++], str + p1 , i - p1);   
         }
     }
}

void write_(int rez) {
     printf("%d", rez);    
}

int main() {        
     freopen("evaluare.in", "r", stdin);
     freopen ("evaluare.out", "w", stdout); 
          
     read_();
     
     getElements();      
     infix2postfix();
     
     int r; 
     r = solve_();     
     write_(r);
     
     return 0;     
}