Cod sursa(job #608890)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 18 august 2011 16:06:59
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.93 kb
#include <fstream>
#include <iostream>
#include <stack>

#define MAXN 100000

using namespace std;

string expr;

inline int priority(const char op)
{
	switch (op)
	{
		case '+':
		case '-':
		{
			return 4;
		}; break;
		
		case '*':
		case '/':
		{
			return 3;
		}; break;
		
		default:
		{
			return 16;
		}
	}
	
	return 16;
}

void ShuntingYard(const string& input, string& output)
{
	char ch;
	int currentNumber = 0;
	stack<char> stOps;

	for (int i=0; i<input.length(); ++i)
	{
		switch (input[i])
		{
			case '(':
			{
				stOps.push(input[i]);
			}; break;

			case ')':
			{
				while ((ch = stOps.top()) != '(')
				{
					stOps.pop();
					output.append(1, ch);
				}
				stOps.pop();
			}; break;
			
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
			{
				output.append(1, input[i]);
			}; break;
			
			default:
			{
				int inserted=0;
				
				while (!stOps.empty())
				{
					ch = stOps.top();
					
					if (priority(ch) <= priority(input[i]))
					{
						//cout << "Add " << ch << endl;
						output.append(1, ch);
						stOps.pop();
						inserted++;
					}
					else
					{
						break;
					}
				}
				
				if (!inserted && !stOps.empty())
				{
					//cout << "added space " << inserted << endl;
					output.append(" ");
				}

				stOps.push(input[i]);
			}
		}
	}
	
	while (!stOps.empty())
	{
		output.append(1, stOps.top());
		stOps.pop();
	}
}

inline int do_operation(const char op, const int var1, const int var2)
{
	int res;
	
	switch (op)
	{
		case '+':
			return var1 + var2;
		case '-':
			return var1 - var2;
		case '*':
			return var1 * var2;
		case '/':
			return var1 / var2;
	}
	
	return 0;
}

int evaluate(const string& expr)
{
	int result, currentNumber=0;
	stack<int> st;
	
	for (int i=0; i<expr.length(); ++i)
	{
		switch (expr[i])
		{	
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
			{
				currentNumber = currentNumber*10 + (expr[i] - 48);
			}; break;
			
			case ' ':
			{
				st.push(currentNumber);
				currentNumber = 0;
			}; break;
			
			default:
			{
				const int var = st.top();
				
				st.pop();
				
				if (expr[i-1]>='0' && expr[i-1]<='9')
				{
					st.push(do_operation(expr[i], var, currentNumber));
				}
				else
				{
					const int var2 = st.top();
					
					st.pop();
					st.push(do_operation(expr[i], var, var2));
				}
				
				currentNumber = 0;
			}
		}
	}
	
	return st.top();
}

int main()
{
	string rpn;
	fstream fin("evaluare.in", fstream::in);
	fstream fout("evaluare.out", fstream::out);
	
	fin >> expr;
	fin.close();

	//cout << expr << endl;

	ShuntingYard(expr, rpn);
	
	//cout << rpn << endl;
	
	fout << evaluate(rpn) << endl;
	
	return 0;
}