Cod sursa(job #1613816)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 25 februarie 2016 17:31:14
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int baza = -1000000000,
	adds = baza-1, subs = baza-2, ori = baza-3,
	open_paren = baza-4, close_paren = baza-5,
	impart = baza-6;

int priority(const int x){
	if(x == adds || x == subs){
		return 1; }
	else if(x == ori || x == impart){
		return 2; } }

int get_num(const string& str, int& x){
	int rez = 0;
	for( ; x < str.size() && isdigit(str[x]); ++x){
		rez = 10 * rez + str[x] - '0'; }
	return rez; }

void tokenize(const string& str, vector<int>& out){
	for(int i = 0; i < str.size(); ){
		if(isdigit(str[i])){
			out.push_back(get_num(str, i)); }
		else if(str[i] == '+'){
			out.push_back(adds);
			++i; }
		else if(str[i] == '-'){
			out.push_back(subs);
			++i; }
		else if(str[i] == '*'){
			out.push_back(ori);
			++i; }
		else if(str[i] == '/'){
			out.push_back(impart);
			++i; }
		else if(str[i] == '('){
			out.push_back(open_paren);
			++i; }
		else if(str[i] == ')'){
			out.push_back(close_paren);
			++i; } } }

void mk_polish(const vector<int>& v, vector<int>& out){
	// polish can into space

	vector<int> st;
	for(int i = 0; i < v.size(); ++i){
		if(v[i] == open_paren){
			st.push_back(open_paren); }
		else if(v[i] == close_paren){
			while(st.back() != open_paren){
				out.push_back(st.back());
				st.pop_back(); }
			st.pop_back(); }
		else if(v[i] < baza){
			while(!st.empty() && priority(st.back()) >= priority(v[i])){
				out.push_back(st.back());
				st.pop_back(); }
			st.push_back(v[i]); }
		else{
			out.push_back(v[i]); } }
	while(!st.empty()){
		out.push_back(st.back());
		st.pop_back(); } }

void eval_polish(vector<int>& st){
	if(st.back() >= baza){
		return; }
	const int op = st.back();
	st.pop_back();

	eval_polish(st);
	const int right = st.back();
	st.pop_back();

	eval_polish(st);
	const int left = st.back();
	st.pop_back();

	if(op == adds){
		st.push_back(left + right); }
	if(op == subs){
		st.push_back(left - right); }
	if(op == ori){
		st.push_back(left * right); }
	if(op == impart){
		st.push_back(left / right); } }


int main(){
	ifstream f("evaluare.in");
	ofstream g("evaluare.out");
	string str;
	f >> str;
	vector<int> v;

	tokenize(str, v);
	vector<int> st;

	mk_polish(v, st);

	eval_polish(st);

	g << st.back() << endl;

	return 0; }