Cod sursa(job #916978)

Utilizator b_ady20Branescu Adrian b_ady20 Data 17 martie 2013 03:55:37
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
#include<cstdio>
#define dim 100001
using namespace std;
template<typename T, int N>
class Stack {
public:
// constructor
Stack() {
// TODO: initializari
	topLevel=-1;
}
// destructor
~Stack() {
// TODO: eliberare resurse, daca este cazul
}
// operator de adaugare
void push(T x) {
// TODO: verificari, implementare
	if(topLevel<N-1)
		stackArray[++topLevel]=x;
}
// operatorul de stergere
T pop() {
// TODO: verificari, implementare
	if(topLevel>-1)
		return stackArray[topLevel--];
	return -1;
}
// operatorul de consultare
T peek() {
// TODO: verificari, implementare
	if(topLevel>-1)
		return stackArray[topLevel];
	return -1;
}
// operatorul de verificare dimensiune
int isEmpty() {
// TODO: implementare
	return (topLevel==-1);
}
private:
// vectorul de stocare
T stackArray[N];
// pozitia in vector a varfului stivei
int topLevel;
};
int prec(char ch){
	if(ch=='+'||ch=='-') return 1;
	else
		if(ch=='*'||ch=='/') return 2;
	else
		if(ch=='^') return 3;
	return 0;
}
bool m_e(char a, char b){
	return prec(a)>=prec(b);
}
int make(int op1, int op2, char ch){
	switch(ch){
		case '+': return op1+op2;
		case '-': return op1-op2;
		case '*': return op1*op2;
		case '/': return op1/op2;
		case '^': if(!op2) return 1; else return op1*make(op1,op2-1,ch);
	}
	return 0;
}
char afis[dim*2];
int main(){
	Stack<char,dim>stiva;
	Stack<int,dim>stiva2;
	int nr,op1,op2;
	char ch;
	int n=0;
	freopen("evaluare.in","r",stdin);
	freopen("evaluare.out","w",stdout);
	while(scanf("%c",&ch)>0&&ch!='\n'){
		if(ch>='0'&&ch<='9'){
			while(ch>='0'&&ch<='9'){
				//printf("%c",ch); 
				afis[n++]=ch;
				scanf("%c",&ch);
			}
			//printf(" ");
			afis[n++]=' ';
		}
		if(ch=='\n') break;
		if(ch=='(') 
			stiva.push(ch);
		else
			if(ch==')'){
				while(!stiva.isEmpty()&&stiva.peek()!='(')
					//printf("%c",stiva.pop());
					afis[n++]=stiva.pop();
				/*if(stiva.isEmpty()){
					fprintf(stderr,"Error 103 - Illegal expression\n");
					return 103;
				}
				else*/
				if(!stiva.isEmpty())
					stiva.pop();
			}
			else{
				while(!stiva.isEmpty()&&prec(stiva.peek())&&m_e(stiva.peek(),ch)){
					if(prec(ch)==prec(stiva.peek())&&prec(ch)==3) break;
					//printf("%c",stiva.pop());
					afis[n++]=stiva.pop();
				}
				stiva.push(ch);
			}
	}
	while(!stiva.isEmpty())
		/*if(stiva.peek()=='('){
			fprintf(stderr,"Error 103 - Illegal expression\n");
			return 103;
		}
		else*/			
			//printf("%c",stiva.pop());
		afis[n++]=stiva.pop();
	int i=0;
	while(i<n){
		ch=afis[i];
		++i;
		if(ch>='0'&&ch<='9'&&i<n){
			nr=0;
			while(ch>='0'&&ch<='9'){
				nr=nr*10+ch-'0';
				//scanf("%c",&ch);
				ch=afis[i];
				++i;
			}
			stiva2.push(nr);
		}
		else
			if(ch!=' '){
				op1=stiva2.pop();
				op2=stiva2.pop();
				stiva2.push(make(op2,op1,ch));
			}
	}
	printf("%d",stiva2.pop());
	return 0;
}