Cod sursa(job #768634)

Utilizator mi5humihai draghici mi5hu Data 17 iulie 2012 15:43:33
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 4.2 kb
#include <stdio.h>
#include <fstream>
#include <stack>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <cstdlib>

#define NMAX 100001

using namespace std;

string read_() {
     string s;
     ifstream fin("evaluare.in");
     fin >> s;
     fin.close(); 
     return s; 
}

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); 
         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;       
    } else {
       return 0;    
    }    
}

queue<string> infix2postfix( vector<string> IF) {
     queue<string> PF;
     stack<string> 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] == ')') {
             string el = myStack.top();
             myStack.pop();
                          
             int crt = 0;
             while (el[0] != '(' && crt++ < 10) {
                  PF.push(el);
                  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]))) {
                     PF.push(myStack.top());
                     myStack.pop();      
                }       
                myStack.push(IF[pozI++]);
            }                     
         } else {
            pozI++;       
         }
     }        
     while (!myStack.empty()) {
         PF.push(myStack.top());
         myStack.pop();      
     }
     return PF;
}

int solve_(queue<string> PF) {
     stack<int> S;
     while (!PF.empty()) {
           string el = PF.front();
           PF.pop();
           //printf("%s ", el.c_str());
           if (isdigit(el[0])) {
               S.push(atoi(el.c_str()));                    
           } else {
               int e1 = S.top();
               S.pop();
               int e2 = S.top();
               S.pop();
               int tmp = eval(e1, e2, el[0]);
               S.push(tmp);     
               //printf("\n%d %d %c => %d\n", e1, e2, el[0], tmp);                                
           }
                 
     }
     return S.top();       
} 

vector<string> getElements(string s) {
     vector<string> IF;
     for (int i = 0; i < s.length(); i++) {
         if (isOperator(s[i]) || isParanthesis(s[i])) {
             string str;
             str.append(&s[i], 1);
             IF.push_back(str);                         
         } else if (isdigit(s[i])) {
             int p1 = i;
             while (i < s.length() && isdigit(s[i])) {
                 i++;      
             }    
             string str;   
             str.append(&s[p1], i - p1);
             IF.push_back(str);
             i--;
         }
     }
     return IF;
}

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

int main() {    
     freopen ("evaluare.out", "w", stdout); 
          
     string s;
     s = read_();
     
     vector<string> IF;
     IF = getElements(s);
     
     queue<string>PF;
     PF = infix2postfix(IF);
      
     int r; 
     r = solve_(PF);
     write_(r);
          
     return 0;     
}