Pagini recente » Borderou de evaluare (job #432883) | Monitorul de evaluare | Borderou de evaluare (job #1769969) | Borderou de evaluare (job #1566377) | Cod sursa (job #2761403)
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;
struct Token {
enum Type {
CHAR,
NUM,
} type;
const int 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, stoi(s.substr(cursor, i - cursor))});
}
}
if (state == ONECHAR) {
if ('0' <= c && c <= '9') {
state = READINT;
cursor = i;
} else {
tokens.push_back(Token{Token::CHAR, c});
}
}
}
if (state == READINT) {
tokens.push_back(Token{Token::NUM, stoi(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 tok.val;
}
if (tok.type == tok.CHAR) {
int r = _execute(postfix, --idx);
int l = _execute(postfix, --idx);
switch (tok.val) {
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;
}