Cod sursa(job #978935)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 30 iulie 2013 15:16:47
Problema Evaluarea unei expresii Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include<stdio.h>
#include<cstring>
#include<stdlib.h>
#include<ctype.h>
#include<stack>
#define NMAX 100001
using namespace std;

char str[NMAX];
stack<struct Elem> stk;
stack<int> spol;
long long 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 eval(char op){
	int x = spol.top();
	spol.pop();
	if(!spol.empty()){
		int y = spol.top();
		spol.pop();
		switch(op){
			case '+': return x + y;
			case '-': return y - x;
			case '*': return x * y;
			case '/': return y / x;
		}
	}
}

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;
	int op1, op2;
	i = 0;
	while(i < N-1){
		if(str[i] == ')'){
			if(!stk.empty())
				vf = stk.top();

			while(!stk.empty() && vf.info != '('){
				stk.pop();
				result = eval(vf.info);
				spol.push(result);
				
				if(!stk.empty())
					vf = stk.top();					
			}
			stk.pop();
			i++;
		}
		else		
			if(isalnum(str[i])){
				nr = atoi(&str[i]);
				spol.push(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();
						result = eval(vf.info);
						spol.push(result);

						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();
		result = eval(vf.info);
		spol.push(result);
		
		if(!stk.empty())
			vf = stk.top();
	}
}			 

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

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

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

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