Cod sursa(job #1455792)

Utilizator aimrdlAndrei mrdl aimrdl Data 29 iunie 2015 03:06:08
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stack>

using namespace std;

#define MAX 100005
#define IS_OP (a) ((a) == '+' || (a) == '-' || (a) == '*' || (a) == '/')

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

char * genPostfix (char *in) {
	int i = 0, l = strlen(in);
	
	if (in[l-1] == '\n') {
		in[l-1] = '\0';
		--l;
	}
	
	char *postfix = new char[2*MAX], *p = postfix;
	
	stack <char> S;
	while (i < l) {
		if (in[i] >= '0' && in[i] <= '9') {			
			while (in[i] >= '0' && in[i] <= '9') {
				*p = in[i];
				++p; ++i;
			}
			*p = ' '; ++p;
		} else {
			if (in[i] == '(') {
				S.push(in[i]);
			} else if (in[i] == ')') {
				while (S.top() != '(') {
					*p = S.top();++p;
					*p = ' '; ++p;
					S.pop();
				}
				S.pop();
			} else {
				int aux = prio(in[i]);
				while (!S.empty() && (prio(S.top()) >= aux)) {
					*p = S.top(); ++p;
					*p = ' ', ++p;
					S.pop();						
				}
				S.push(in[i]);
			}
			++i;
		}
	} 	
	
	while (!S.empty()) {
		*p = S.top(); ++p;
		*p = ' '; ++p;
		S.pop();
	}
	*p = '\0';
	return postfix;
}

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

long eval (char *s) {
	int l = strlen(s), i = 0;
	
	stack <long> S;
	while (i < l) {
		if (s[i] >= '0' && s[i] <= '9') {
			char *aux = &s[i];
			while (s[i] >= '0' && s[i] <= '9') ++i;
			s[i] = '\0';
			S.push(atol(aux));
		} else if (s[i] != ' ') {
			long b = S.top(); S.pop();
			long a = S.top(); S.pop();
			long r = op(a, b, s[i]);
			S.push(r);
		}
		++i;
	}
	
	long r = S.top();
	
	return r; 
}
		

			
int main (void) {
	freopen("evaluare.in", "r", stdin);
	freopen("evaluare.out", "w", stdout);
	
	char *in = new char[MAX];
	fgets(in, MAX, stdin);

	char *postfix = genPostfix(in);
	delete[] in;
	
	long r = eval(postfix);
	printf("%ld", r);
	
	delete[] postfix;
	return 0;
}