Cod sursa(job #978776)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 29 iulie 2013 17:55:36
Problema Evaluarea unei expresii Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include<stdio.h>
#include<cstring>
#include<stdlib.h>
#include<ctype.h>
#include<vector>
#include<stack>
#define NMAX 100001
using namespace std;

char str[NMAX];
stack<struct Elem> stk;
stack<int> stkr;
vector<int> vpol;
int result;

struct Elem{
	char info;
	int prio;
};

int priority(char op){
	switch(op){
		case '(': return 0;
		case '+': return 1;
		case '-': return 1;
		case '*': return 2;
		case '/': return 2;
	}
}

int integer(char op){
	switch(op){
		case '+': return -1;
		case '-': return -2;
		case '*': return -3;
		case '/': return -4;
	}
}

int no_digits(int nr){
	if(nr == 0)
		return 0;
	else
		return 1 + no_digits(nr/10);
}

void polish_form(){
	int i, N = strlen(str), nr;
	struct Elem aux, aux2, vf;
	i = 0;
	while(i < N){
		if(str[i] == ')'){
			if(!stk.empty())
				vf = stk.top();

			while(!stk.empty() && vf.info != '('){
				stk.pop();	
				vpol.push_back(integer(vf.info));
				
				if(!stk.empty())
					vf = stk.top();					
			}
			stk.pop();
			i++;
		}
		else		
			if(isalnum(str[i])){
				nr = atoi(&str[i]);
				vpol.push_back(nr);
				i = i + no_digits(nr);
			}
			else
				if(str[i] == '('){
					aux.info = str[i];
					aux.prio = priority(str[i]);
					stk.push(aux);
					i++;
				}
				else{
					aux.prio = priority(str[i]);
					aux.info = str[i];

					if(!stk.empty())
						vf = stk.top();

					while(!stk.empty() && vf.prio >= aux.prio){
						stk.pop();
						vpol.push_back(integer(vf.info));
						if(!stk.empty())
							vf = stk.top();
					}
					stk.push(aux);
					i++;
				}
	}

	if(!stk.empty())
		vf = stk.top();
	while(!stk.empty() && vf.info != '('){
		aux = stk.top();
		stk.pop();
		vpol.push_back(integer(aux.info));
		
		if(!stk.empty())
			vf = stk.top();
	}
}			 

void evaluate(){
	int i;
	int op1, op2, op;
	for(i = 0; i < vpol.size() - 1; i++){		
			if(vpol[i] >= 0){
				stkr.push(vpol[i]);
			}
			else{
				op1 = stkr.top();
				stkr.pop();
				if(!stkr.empty()){
					op2 = stkr.top();
					stkr.pop();
					
					if(vpol[i] == -1)
						result = op1 + op2;
					else
						if(vpol[i] == -2)
							result = op2 - op1;
						else
							if(vpol[i] == -3)
								result = op1 * op2;
							else
								if(vpol[i] == -4)
									result = op2 / op1;
	
					stkr.push(result);
				}
			}
	}
}	

int main(){
	FILE *pf, *pg;
	int i;
	pf = fopen("evaluare.in", "r");
	pg = fopen("evaluare.out", "w");

	fgets(str, sizeof(str), pf);
	polish_form();
	evaluate();

	fprintf(pg, "%d", result);

	fclose(pf);
	fclose(pg);
	return 0;
}