Cod sursa(job #723103)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 24 martie 2012 22:06:56
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <map>
#include <stack>
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
const int DIM = 100005;

char infix[DIM], postfix[DIM];
map<char, int> priority; // operator priority

bool isop(char c){
	return c == '*' or c == '/' or c == '+' or c == '-';
}

void shunting_yard(){
	stack<char> s; //stack of operators
	int i, // iterator over infix
		j; //iterator over postfix;
	
	for( i = 0, j = 0; i < strlen(infix); ){
		if( infix[i] >= '0' and infix[i] <= '9'){ // If we have a digit
			while( infix[i] >= '0' and infix[i] <= '9'){ // We construct the number
				postfix[j] = infix[i];
				i++, j++;
			}
			postfix[j++] = ' '; // space is separator			
		}
		else if(isop(infix[i])){ // If we have an operator
			while( s.empty()==0 and priority[infix[i]] <= priority[s.top()]){
				postfix[j++] = s.top();
				postfix[j++] = ' ';
				s.pop();
			}
			s.push(infix[i++]);
		}
		else if( infix[i] == '(')
			s.push(infix[i++]);
		else if( infix[i] == ')'){
			while(s.top() != '('){
				postfix[j++] = s.top();
				postfix[j++] = ' ';
				s.pop();
			}
			s.pop(); // pop '('
			i++;
		}
	}
	while(not s.empty()){
		postfix[j++] = s.top();
		postfix[j++] = ' ';
		s.pop();
	}
}

int interpret(){
	stack<int> s;
	int i = 0;
	while( i < strlen(postfix)){
		if( postfix[i]>= '0' and postfix[i] <= '9'){ // If we have digit
			char number[15];
			int ni = 0;
			while(postfix[i]>= '0' and postfix[i] <= '9'){
				number[ni++] = postfix[i++];
			}
			number[ni] = (char) 0;
			int a = atoi(number);
			s.push(a);
		}
		else if( isop(postfix[i])){ // If we have operator
			int b = s.top();
			s.pop();
			int a = s.top();
			s.pop();
			int c;
			switch (postfix[i])
			{
				case '+':{ 
					c = a+b; 
					break;
				}
				case '-':{
					c = a-b;
					break;
				}
				case '*':{
					c = a*b;
					break;
				}
				case '/':{
					c = a/b;
					break;
				}
			}
			s.push(c);
			i++;
		}
		else i++;
	}
	return s.top();
}

int main(){

	fin.getline(infix, DIM);
	priority['*'] = 2;
	priority['/'] = 2;
	priority['+'] = 1;
	priority['-'] = 1;
	shunting_yard();
	fout << interpret();
	return 0;
}