Cod sursa(job #1199378)

Utilizator howsiweiHow Si Wei howsiwei Data 19 iunie 2014 06:07:06
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <unordered_map>
#include <cctype>
using namespace std;

struct Node
{
	bool isnum;
	union {
		int num;
		char op;
	};
	Node *left, *right;
	Node (int num) : num(num)
	{
		isnum = true;
	}
	Node (char op, Node *left, Node * right) : op(op), left(left), right(right)
	{
		isnum = false;
	}
};

int apply(char op, int x, int y)
{
	switch (op) {
		case '+': return x+y;
		case '-': return x-y;
		case '*': return x*y;
		case '/': return x/y;
		default: return 0;
	}
}

void reduce(stack<char>& ops, stack<Node*>& pnodes)
{
	char op = ops.top();
	ops.pop();
	Node *pnode = pnodes.top();
	pnodes.pop();
	pnodes.top() = new Node(op, pnodes.top(), pnode);
}

int eval(Node *pnode)
{
	if (pnode->isnum) {
		return pnode->num;
	}
	else {
		return apply(pnode->op, eval(pnode->left), eval(pnode->right));
	}
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("evaluare.in", "r", stdin);
	freopen("evaluare.out", "w", stdout);
	unordered_map<char, int> precedence = {{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
	string expr;
	getline(cin, expr);
	expr = '('+expr+')';
	stack<char> ops;
	stack<Node*> pnodes;
	for (auto it = expr.begin(); it != expr.end(); ) {
		if (isdigit(*it)) {
			int num = 0;
			do {
				num = num*10+*it-'0';
				++it;
			} while (isdigit(*it));
			pnodes.push(new Node(num));
		}
		else {
			if (*it == '(') {
				ops.push(*it);
			}
			else if (*it == ')') {
				while (ops.top() != '(') {
					reduce(ops, pnodes);
				}
				ops.pop();
			}
			else {
				while (precedence[ops.top()] >= precedence[*it]) {
					reduce(ops, pnodes);
				}
				ops.push(*it);
			}
			++it;
		}
	}
	printf("%d\n", eval(pnodes.top()));
	return 0;
}