Cod sursa(job #1587761)

Utilizator sebii_cSebastian Claici sebii_c Data 2 februarie 2016 16:13:16
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <fstream>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

/**@brief Converts from infix to postfix notation.
 */
string to_postfix(const string& infix) {
    stringstream output;
    stack<char> ops;
    
    string::const_iterator it = infix.begin();
    while (it != infix.end()) {
	if (*it == '(') {
	    ops.push(*it);
	    ++it;
	} else if (*it == ')') {
	    while (!ops.empty()) {
		char c = ops.top(); ops.pop();
		if (c == '(')
		    break;
		else
		    output << c << " ";
	    }
	    ++it;
	} else if (*it == '+' || *it == '-') {
	    while (!ops.empty()) {
		char c = ops.top();
		if (c == '+' || c == '-' || c == '*' || c == '/') {
		    ops.pop();
		    output << c << " ";
		} else {
		    break;
		}
	    }
	    ops.push(*it);
	    ++it;
	} else if (*it == '*' || *it == '/') {
	    while (!ops.empty()) {
		char c = ops.top();
		if (c == '*' || c == '/') {
		    ops.pop();
		    output << c << " ";
		} else {
		    break;
		}
	    }
	    ops.push(*it);
	    ++it;
	} else if (*it >= '0' && *it <= '9') {
	    int num = 0;
	    while (*it >= '0' && *it <= '9') {
		num = num * 10 + (*it - '0');
		++it;
	    }
	    output << num << " ";
	}
    }
    while (!ops.empty()) {
	output << ops.top() << " ";
	ops.pop();
    }

    return output.str();
}

/**@brief Evaluate an expression written in postfix notation.
 */
int eval(const string& postfix) {
    string::const_iterator it = postfix.begin();
    stack<int> eval_stack;

    while (it != postfix.end()) {
	if (*it == ' ') {
	    ++it;
	} else if (*it >= '0' && *it <= '9') {
	    int num = 0;
	    while (*it >= '0' && *it <= '9') {
		num = num * 10 + (*it - '0');
		++it;
	    }
	    eval_stack.push(num);
	} else if (*it != ' ') {
	    int fst = eval_stack.top(); eval_stack.pop();
	    int scd = eval_stack.top(); eval_stack.pop();
	    switch (*it) {
	    case '+':
		eval_stack.push(fst + scd);
		break;
	    case '-':
		eval_stack.push(scd - fst);
		break;
	    case '*':
		eval_stack.push(fst * scd);
		break;
	    case '/':
		eval_stack.push(scd / fst);
		break;
	    }
	    ++it;
	}
    }

    return eval_stack.top();
}

int main() {
    ifstream fin("evaluare.in");
    ofstream fout("evaluare.out");

    string infix;
    fin >> infix;
    auto postfix = to_postfix(infix);
    auto result = eval(postfix);

    fout << result;
    
    return 0;
}