Cod sursa(job #447570)

Utilizator GodiesVlad Voicu Godies Data 29 aprilie 2010 01:43:04
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <iostream>
#include <cstring>      
#include <vector>

#define NMAX 100000

typedef struct {
	int type;
	union {
		int i;
		char s;
	} u;
}Union;

using namespace std;

int isoperator(char s)
{
	if (s == '*' || s == '+' || s == '-' || s == '/')
		return 1;
	return 0;
}

int pri(char s)
{
	if ((s == '*') || (s == '/'))
		return 2;
	return 1;
}               

vector<Union> rpm(char* s)
{
	Union a;
	int size = strlen(s), i;
	stack<char> op;
	vector<Union> final;   
	for (i = 0; i < size; i++) {
		if (isdigit(s[i])) {
			a.u.i = 0;
			a.type = 1;
			while (isdigit(s[i])) {
				a.u.i = a.u.i * 10 + (s[i] - '0'); 
				i++;
			}
			i--;
			final.push_back (a);
		}
		if (isoperator(s[i]))
		{
			if(op.size() != 0) {
				if (isoperator(op.top()) &&
						((pri(s[i])) <=
							pri(op.top()))) 
				{
					a.type = 2;
					a.u.s = op.top();
					final.push_back (a);
					op.pop();
				}
			}
			op.push(s[i]);
		}
		if (s[i] == '(')
			op.push(s[i]);
		if (s[i] == ')') {
			while (op.top() != '(')
			{                  
				a.type = 2;
				a.u.s = op.top();
				final.push_back(a);
				op.pop();
			}
			op.pop();
		}
	}
	while (op.size() != 0)
	{          
  		a.type = 2;		
		a.u.s = op.top();
		final.push_back(a);
		op.pop();
	}
	return final;
}

int evaluate (vector<Union> v) 
{
	vector<Union>::iterator it;
	stack<int> st;
	int result;
	int val1, val2;
	for (it = v.begin(); it < v.end(); it++) {
	       if (it->type == 1)
                       st.push(it->u.i);
	       else {           
		       val1 = st.top();
		       st.pop();
		       val2 = st.top();
		       st.pop();
		       if (it->u.s == '-') 
			       result = val1 - val2; 
		       if (it->u.s == '+') 
			       result = val1 + val2;
		       if (it->u.s == '/')
			       result = val2 / val1;
		       if (it->u.s == '*')
			       result = val1 * val2;
		       st.push(result);
	       }
	}
	result = st.top();
	st.pop();
	return result;
}

int main()
{
	char *s = new char[NMAX];
	vector<Union> v;
	vector<Union>::iterator it;
	FILE *f = freopen("evaluare.in", "rt", stdin);
	FILE *g = freopen("evaluare.out", "wt", stdout);
	scanf ("%s" , s);
	v = rpm(s);   
	for (it = v.begin(); it < v.end(); it++) {
		if (it->type == 1)
			cout << it->u.i;
		else
			cout << it->u.s;
	} 
	cout << endl  << evaluate(v) << endl;
	fclose(f);
	fclose(g);
	delete[] s;
	return 0;
}