Pagini recente » Cod sursa (job #432258) | Cod sursa (job #523365) | Cod sursa (job #558203) | Clasamentul arhivei de probleme | Cod sursa (job #2761402)
#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;
}