Cod sursa(job #582550)

Utilizator varuvasiTofan Vasile varuvasi Data 15 aprilie 2011 15:53:00
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.03 kb
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

#define maxn 200022

char e[maxn];
stack<char> process_stack;
stack<int> st;
vector<string> postfix;

int is_variable(char c)
{
	return (c >= '0' && c <= '9');	
}

string get_next_variable(int i)
{
	string v = "";
	while (i < strlen(e) && is_variable(e[i]))
		v += e[i], i++;
	return v;
}

int is_operator(char c)
{
	return (c == '+' || c == '-' || c == '/' || c == '*');
}

int is_symbol(char c)
{
	return is_operator(c) || (c == '(' || c == ')');
}

int greater_operator(int op1, int op2)
{
	int val1 = (op1 == '*' || op1 == '/');
	int val2 = (op2 == '*' || op2 == '/');
	if (val1 > val2) 
		return 1;
	else 
		if (val1 < val2) 
			return -1;
	return 0;
}

void process_infix()
{
	int len_exp = strlen(e), i = 0, k = 0;
	cout << len_exp;
	for (i = 0; i < len_exp; i++)
	{
		if (is_variable(e[i])) // variables are copied to the output
		{
			string var = get_next_variable(i);
			postfix.push_back(var);
			i += var.size() - 1;
		}
		else
			if (is_symbol(e[i]))
			{
				if (e[i] == '(')
					process_stack.push(e[i]);
				else if (e[i] == ')')
				{
					while (process_stack.top() != '(')
					{
						postfix.push_back(string() +  process_stack.top());
						process_stack.pop();
					}
					process_stack.pop();
				}
				else if (is_operator(e[i]))
				{
					if (process_stack.empty())
						process_stack.push(e[i]);
					else
					{
						while (!process_stack.empty() && 
								process_stack.top() != '(' && 
								greater_operator(process_stack.top(), e[i]) >= 0)
						{
							postfix.push_back(string() + process_stack.top());
							process_stack.pop();
						}
						process_stack.push(e[i]);
					}
				}
			}
	}
	while (!process_stack.empty())
	{
		postfix.push_back(string() + process_stack.top());
		process_stack.pop();
	}
}

int is_operator(string s)
{
	return is_operator(s[0]);
}

int is_variable(string s)
{
	return is_variable(s[0]);
}

int compute_by_operator(int var1, int var2, string _op)
{
	char op = _op[0];
	int new_var = 0;
	if (op == '+') new_var = var2 + var1;
	if (op == '-') new_var = var2 - var1;
	if (op == '/') new_var = var2 / var1;
	if (op == '*') new_var = var2 * var1;
	return new_var;
}

int compute_postfix()
{
	int i;
	for (i = 0; i < postfix.size(); i++)
	{
		if (is_variable(postfix[i]))
			st.push(atoi(postfix[i].c_str()));
		else
		{
			int var1 = st.top(); st.pop();
			int var2 = st.top(); st.pop();

			int new_val = compute_by_operator(var1, var2, postfix[i]);
			st.push(new_val);
		}
	}
	return st.top();
}

int main()
{
	int i;
	FILE *fin = fopen("evaluare.in", "rt");
	FILE *fout = fopen("evaluare.out", "wt");

	fscanf(fin, "%s", e);
	//fprintf(fout, "%s\n", e);

	process_infix();
	
	//for (i = 0; i < postfix.size(); i++)
	//	fprintf(fout, "%s ", postfix[i].c_str());

	int total = compute_postfix();
	fprintf(fout, "%d", total);

	return 0;
}