Cod sursa(job #1237698)

Utilizator vtt271Vasile Toncu vtt271 Data 4 octombrie 2014 17:38:50
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

ifstream inFile("file.in");
ofstream outFile("evaluare.out");

void get_canonica_form(char* expresion, char* canonical)
{
	char* e = expresion;
	char* c = canonical;

	while(*e){
		if(*e < '0' || *e > '9'){
			*c = *e;
			c++;
			e++;
		}else{
			*c = 'o';
			c++;
			while(*e >= '0' && *e <= '9'){
				e++;
			}
		}
	}
	*c = '\0';
}

void get_polish_form(char* canonical, char* polish)
{
	stack <char> S;

	char* c = canonical;
	char* p = polish;

	while(*c){
		if(*c == 'o'){
			*p = 'o';
			p++;
			c++;
		}else{
			if(*c == '('){
				S.push(*c);
				c++;
			}

			if(*c == '+' || *c == '-'){
				while(!S.empty() && S.top() != '('){
					*p = S.top();
					p++;
					S.pop();
				}
				S.push(*c);
				c++;
			}

			if(*c == '*' || *c == '/'){
				while(!S.empty() && S.top() != '+' && S.top() != '-' && S.top() != '('){
					*p = S.top();
					p++;
					S.pop();
				}
				S.push(*c);
				c++;
			}

			if(*c == ')'){
				while(S.top() != '('){
					*p = S.top();
					p++;
					S.pop();
				}
				S.pop();
				c++;
			}

		}
	}
	
	while(!S.empty()){
		*p = S.top();
		p++;
		S.pop();
	}

	*p = '\0';
}

void get_numbers(char* expresion, vector <int> &numbers)
{
	char* e = expresion;
	while(*e){
		if(*e >= '0' && *e <= '9'){
			int aux = 0;
			while(*e >= '0' && *e <= '9'){
				aux = aux*10 + (*e - '0');
				e++;
			}
			numbers.push_back(aux);
		}else{
			e++;
		}
	}
}

int evaluate(char* polish, vector <int> numbers)
{
	stack <int> S;

	int i = 0;
	char* p = polish;

	while( *p ){
		if(*p == 'o'){
			S.push(numbers[i++]);
		}else{
			int a = S.top();
			S.pop();
			int b = S.top();
			S.pop();

			switch (*p)
			{
			case '+': S.push(a+b);
				break;
			case '-': S.push(a-b);
				break;
			case '*': S.push(a*b);
				break;
			case '/': S.push( b/a);
				break;
			}
		}
		p++;
	}

	return S.top();
}

int main()
{
	char expresion[100005];
	char canonical[100005], polish[100005];
	vector <int> numbers;

	inFile >> expresion;

	get_canonica_form(expresion, canonical);
	get_polish_form(canonical, polish);
	get_numbers(expresion, numbers);

	outFile << evaluate(polish, numbers) << "\n";

}