Cod sursa(job #1225238)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 2 septembrie 2014 00:46:42
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <ctype.h>
#include <cstdlib>  
#include <stack>
using namespace std;

struct elem{
	bool isOp; // true if is '+'..
	int nr;
	char op;
};

char str[100000];
struct elem elems[100000];

int pos;

int value(char c){
	switch(c){
	case '*': case '/': return 1;
	case ')': case '+': case '-': return 0;
	}
}

void polish_notation(){
	stack<char> op;
	int len = strlen(str);
	for(int i = len-1; i >= 0; i--){
		switch(str[i]){
		case ')' : case '*': case '/': op.push(str[i]); break;
		case '(':	
			while(op.top() != ')'){
				char x = op.top();
				elems[pos].isOp = true;
				elems[pos++].op = x;
				op.pop();
			}
			op.pop();
			break;
		case '-' : case '+' : 
			while(op.size()){
				char x = op.top();
				if(value(x) > value(str[i])){
					elems[pos].isOp = true;
					elems[pos++].op = x;
					op.pop();
				}else{
					break;
				}
			}
			op.push(str[i]);
			break;
		default:
			int nr = 0, pow = 1;
			while(i >= 0 && isdigit(str[i])){
				nr = (str[i] - '0')*pow + nr;
				pow *= 10;
				i--;
			}
			elems[pos].isOp = false;
			elems[pos++].nr = nr;
			i++;
			break;
		}
	}
	while(op.size()){
		char x = op.top();
		elems[pos].isOp = true;
		elems[pos++].op = x;
		op.pop();
	}
}

int main(){
	freopen("evaluare.in", "r", stdin);
	freopen("evaluare.out", "w", stdout);
	scanf("%s", str);
	polish_notation();

	stack<int> res;
	stack<char> ops;
	int i = 0;
	while(i < pos){
		if(elems[i].isOp){
			int x1 = res.top(); res.pop();
			int x2 = res.top(), ans; res.pop();
			switch(elems[i].op){	
			case '+': 
				ans = x1+x2;
				break;
			case '-':
				ans = x1 - x2;
				break;
			case '*':
				ans  = x1 * x2;
				break;
			case '/':
				ans  = x1 / x2;
				break;
			}
			res.push(ans);
		}else{
			res.push(elems[i].nr);
		}
		i++;
	}
	cout << res.top() << "\n";
	res.pop();
	return 0;
}