Cod sursa(job #1217091)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 6 august 2014 16:17:15
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <stdio.h>
#include <stack>
//#include <time.h>
using namespace std;

typedef long long ll;
typedef unsigned int uint;
char expr[100010];
uint len;

inline int preceding(char op1, char op2){
	if((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/'))
		return 1;	// op2 mai puternic
	if(op1 == '(')
		return 1;
	return 0;// op1 mai puternic
}
inline ll result( ll nr1, ll nr2, char op){
	switch(op){
		case '+' : return nr1 + nr2;
		case '-' : return nr1 - nr2;
		case '*' : return nr1 * nr2;
		case '/' : return nr1 / nr2;

	}
	return 0;
}
ll getNumber(char nr[], int len){
	ll res = 0;
	int i = 0;
	for(; i < len;){
		res *= 10;
		res += (ll)(nr[i++] - '0');
	}
	return res;
}
void evaluateExpr(){
	stack<ll> numbers;
	stack<char> operators;
	char nr[100],l = 0;
	char op;
	for(uint i = 0; i < len; i++){
	//	cout<<i<<'\n';
		if(expr[i] <= '9' && expr[i] >= '0')
			nr[l++] = expr[i];
		else{
			if(l > 0){
				numbers.push(getNumber(nr,l));
				l = 0;
			}
			if(expr[i] != ')'){
				
				if(expr[i] != '(')
					while(operators.size() > 0 && numbers.size() > 1 && !preceding((op = operators.top()),expr[i]))
					{
						ll nr1 = numbers.top(); numbers.pop();
						ll nr2 = numbers.top(); numbers.pop();
						operators.pop();
						numbers.push(result(nr2,nr1,op));
					}
				operators.push(expr[i]);
			}
			else{
				while((op = operators.top()) != '('){
					ll nr1 = numbers.top(); numbers.pop();
					ll nr2 = numbers.top(); numbers.pop();
					operators.pop();
					numbers.push(result(nr2,nr1,op));
				}
				operators.pop();
			}
		}
	}
	if(l > 0)
		numbers.push(getNumber(nr,l));
	while(operators.size() > 0 && operators.top() != '('){
		ll nr1 = numbers.top(); numbers.pop();
		ll nr2 = numbers.top(); numbers.pop();
		char op = operators.top(); operators.pop();
		numbers.push(result(nr2,nr1,op));
	}
	printf("%lld\n", numbers.top());
}

int main(){
//	clock_t startTime = clock();
	freopen("evaluare.in","r",stdin);
	freopen("evaluare.out","w",stdout);

	fgets(expr,sizeof(expr),stdin);
	len = strlen(expr) - 1;

	evaluateExpr();
	//cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

	return 0;
}