Cod sursa(job #2761401)

Utilizator raikadoCri Lu raikado Data 2 iulie 2021 02:50:04
Problema Evaluarea unei expresii Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.95 kb
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

using namespace std;



struct Token {
	enum Type {
		CHAR,
		NUM,
	} type;

	const string val;
};

vector<Token> tokenize(const string &s) {
	enum State {ONECHAR, READINT};

	State state = ONECHAR;
	size_t cursor = 0;
	vector<Token> tokens;

	for (size_t i = 0; i < s.size(); i++) {
		char c = s[i];

		if (state == READINT) {
			if ('0' <= c && c <= '9')
				continue;
			else {
				state = ONECHAR;
				tokens.push_back(Token{Token::NUM, s.substr(cursor, i - cursor)});
			}
		}

		if (state == ONECHAR) {
			if ('0' <= c && c <= '9') {
				state = READINT;
				cursor = i;
			} else {
				tokens.push_back(Token{Token::CHAR, string(1, c)});
			}
		} 
	}

	if (state == READINT) {
		tokens.push_back(Token{Token::NUM, s.substr(cursor, s.size() - cursor)});
	}

	return tokens;
}

vector<Token> to_postfix(const vector<Token> &tokens) {
	vector<Token> stk;
	vector<Token> postfix;

	for (const Token &tok : tokens) {
		if (tok.type == tok.NUM) {
			postfix.push_back(tok);
		} else {
			if (stk.empty()) {
				stk.push_back(tok);
				continue;
			}

			if (tok.val == "(") {
				stk.push_back(tok);
			} else if (tok.val == ")") {
				while (stk.back().val != "(") {
					postfix.push_back(stk.back());
					stk.pop_back();
				}
				stk.pop_back();
			} else if (tok.val == "*" || tok.val == "/") {
				while (!stk.empty() && (stk.back().val == "*" || stk.back().val == "/")) {
					postfix.push_back(stk.back());
					stk.pop_back();
				}
				stk.push_back(tok);
			} else if (tok.val == "+" || tok.val == "-") {
				while (!stk.empty() && (stk.back().val != "(" && stk.back().val != ")")) {
					postfix.push_back(stk.back());
					stk.pop_back();
				}
				stk.push_back(tok);
			}
		}
	}

	while (!stk.empty()) {
		postfix.push_back(stk.back());
		stk.pop_back();
	}

	return postfix;
}

int _execute(const vector<Token> &postfix, size_t &idx) {
	if (idx > postfix.size()) {
		throw out_of_range("idx < 0");
	}

	const Token &tok = postfix[idx];

	if (tok.type == tok.NUM) {
		return stoi(tok.val);
	}

	if (tok.type == tok.CHAR) {
		int r = _execute(postfix, --idx);
		int l = _execute(postfix, --idx);

		char op = tok.val[0];

		switch (op) {
			case '+':
				return l + r;
			case '-':
				return l - r;
			case '*':
				return l * r;
			case '/':
				return l / r;
		}
	}

	throw logic_error("Unrecognized token type");
}

int execute(const vector<Token> &postfix) {
	size_t idx = postfix.size() - 1;
	return _execute(postfix, idx);
}


int main(int argc, char const *argv[])
{
	ifstream fin("evaluare.in");
	ofstream fout("evaluare.out");

	string s;
	fin >> s;

	vector<Token> tokens = tokenize(s);
	// for (const Token &tok : tokens) {
	// 	cout << tok.val;
	// }
	// cout << endl;

	vector<Token> postfix = to_postfix(tokens);
	// for (const Token &tok : postfix) {
	// 	cout << tok.val << ' ';
	// }
	// cout << endl;

	int result = execute(postfix);
	// cout << result << endl;
	fout << result;

	return 0;
}