Cod sursa(job #2108401)

Utilizator o_micBianca Costin o_mic Data 18 ianuarie 2018 10:40:04
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <stack>
#define DN 10000000
#define LL long long

using namespace std;

stack<int> rpn, ops;

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

// ifstream fin("input.txt");

int op_hash(char op) {
	switch(op) {
		case '+': return -1;
		case '-': return -2;
		case '*': return -3;
		case '/': return -4;
		case '(': return -5;
		case ')': return -6;
	}
}

int op_priority(int op) {
	if (op >= -2) return 1;  // +-
	return 2;  // */
}

bool is_digit(char c) {
	return c >= '0' && c <= '9';
}

int get_token(string &s, int &pos) {
	if (!is_digit(s[pos])) {
		return op_hash(s[pos++]);
	}
	int num = 0;
	while(is_digit(s[pos]))
		num = num * 10 + (s[pos++] - '0');
	return num;
}

void push_operator(int op) {
	if (op == -6) {
		// in case of closed parenthesis, we pop all operators till the open one
		while (!ops.empty() && ops.top() != -5) {
			rpn.push(ops.top());
			ops.pop();
		}
		if (!ops.empty())
			ops.pop();  // pop the opening parenthesis
		return;
	}
	if (op == -5) {
		// opening parenthesis are just pushed on the operator stack
		ops.push(op);
		return;
	}
	while (!ops.empty() && ops.top() >= -4 && op_priority(ops.top()) >= op_priority(op)) {
		rpn.push(ops.top());
		ops.pop();
	}
	ops.push(op);
}

void reverse_polish(string &s) {
	int pos = 0;
	while (pos < s.size()) {
		int token = get_token(s, pos);
		if (token < 0) {
			// token is an operator
			push_operator(token);
		} else {
			// token is a number
			rpn.push(token);
		}
	}
	while(!ops.empty()) {
		rpn.push(ops.top());
		ops.pop();
	}
}

int get_operand() {
	// Returns the last operand from rpn, which can be the result of an expression
	if (rpn.empty()) return 0;  // this should never execute is rpn is valid

	int token = rpn.top();
	rpn.pop();
	if (token < 0) {
		// binary operator, needs 2 operands
		int b = get_operand(), a = get_operand();
		switch(token) {
			case -1: return a + b;
			case -2: return a - b;
			case -3: return a * b;
			case -4: return a / b;
		}
	}
	return token;
}

int main()
{
    string s;
    fin >> s;
    reverse_polish(s);
    fout << get_operand();
    return 0;
}