Cod sursa(job #933202)

Utilizator razyelxrazyelx razyelx Data 29 martie 2013 18:06:15
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.93 kb
#include <fstream>
#include <stack>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

stack<char> st;
string infix;
vector<string> prefix;

bool isOperator(char x) {
	switch (x) {
		case '+':
			return true;
		case '-':
			return true;
		case '/':
			return true;
		case '*':
			return true;
		default:
			return false;			
	}
}

bool isOperator(string x) {
	if (x.compare("+") == 0 || x.compare("-") == 0 ||
		x.compare("*") == 0 || x.compare("/") == 0) {
		return true;
	}
	return false;
}

bool isLeftBracket(char c) {	
	return c == '(';
}

bool isRightBracket(char c) {
	return c == ')';
}

bool greater2(char op1, char op2) {
	if (op1 == '*' || op1 == '/') {
		return true;
	} else if (op2 == '+' || op2 == '-') {
		return true;
	}
	return false;
}	

void convertToPrefix(string infix) {	
	st.push(')');
	string leftBracket = "(";
	infix.insert(0, leftBracket);
	for (int i = infix.size() - 1; i >= 0;) {
		//cout << "Debug: infix[i]=" << infix[i] << endl;
		if (isOperator(infix[i])) {
			char op = st.top();
			//cout << "Operator: op=" << op << endl;
			if (greater2(op, infix[i]) && isOperator(op)) {
				string temp = "";
				temp += op;				
				prefix.push_back(temp);
				st.pop();
			}
			st.push(infix[i]);
			i--;
		} else if (isLeftBracket(infix[i])) {
			while (true) {
				char op = st.top();
				//cout << "Operator: op=" << infix[i] << endl;
				if (isRightBracket(op)) {
					break;
				}
				string temp = "";
				temp += op;				
				prefix.push_back(temp);
				st.pop();
			}
			st.pop();
			i--;
		} else if (isRightBracket(infix[i])) {
			st.push(infix[i]);
			i--;
		} else {
			string t = "";			
			while (infix[i] >= 48 && infix[i] <= 57) {
				string temp = "";
				temp += infix[i];
				t.insert(0, temp);
				i--;
			}
			prefix.push_back(t);
		}
	}
}

long eval(vector<string> expr) {
	stack<long> op;
	for (int i = 0; i < expr.size(); i++) {
		if (!isOperator(expr[i])) {
			long t = 0;
			for (int j = 0; j < (int)expr[i].size(); j++) {
				t = t * 10 + expr[i][j] - 48;
			}
			op.push(t);
			//cout << "Debug t=" << t << endl;
		} else {
			long t1 = op.top();
			op.pop();
			long t2 = op.top();
			op.pop();
			//cout << "Debug t1 op t2 = " << t1 << expr[i] << t2 << endl;
			if (expr[i].compare("+") == 0) {
				op.push(t1 + t2);
			}
			if (expr[i].compare("/") == 0) {
				op.push(t1 / t2);
			}
			if (expr[i].compare("-") == 0) {
				op.push(t1 - t2);
			}
			if (expr[i].compare("*") == 0) {
				op.push(t1 * t2);
			}			
		}
	}
	return op.top();
}

int main() {
	
	ifstream fin("evaluator.in");
	
	while (!fin.eof()) {
		getline(fin, infix);
		convertToPrefix(infix);
	}
	
	/*for (int i = 0; i < prefix.size(); i++) {
		cout << prefix[i] << " ";
	}*/
	
	long result = eval(prefix);
	//cout << "result=" << result; 
	ofstream fout("evaluator.out");
	fout << result;
	return 0;
}