Pagini recente » Cod sursa (job #1173909) | Cod sursa (job #603685) | Cod sursa (job #1105298) | Cod sursa (job #1935441) | Cod sursa (job #2872055)
#include <cctype>
#include <fstream>
#include <optional>
#include <stack>
#include <variant>
#include <vector>
enum Operator { Add, Sub, Mul, Div, LeftParens, RightParens };
using Token = std::variant<Operator, int>;
unsigned precedence(Operator op) {
switch (op) {
case Add:
case Sub:
return 1;
break;
case Mul:
case Div:
return 2;
break;
default:
return 0;
}
}
std::vector<Token> tokenize(const std::string &str) {
std::vector<Token> tokens;
std::optional<int> num_builder = {};
for (auto c : str) {
if (isdigit(c)) {
num_builder = num_builder.value_or(0) * 10 + (c - '0');
} else {
if (num_builder.has_value()) {
tokens.push_back(num_builder.value());
num_builder = {};
}
switch (c) {
case '+':
tokens.push_back(Add);
break;
case '-':
tokens.push_back(Sub);
break;
case '*':
tokens.push_back(Mul);
break;
case '/':
tokens.push_back(Div);
break;
case '(':
tokens.push_back(LeftParens);
break;
case ')':
tokens.push_back(RightParens);
break;
}
}
}
// Push remaining number
if (num_builder.has_value()) {
tokens.push_back(num_builder.value());
}
return tokens;
}
std::vector<Token> convert_to_rpn(const std::vector<Token> &infix) {
std::stack<Operator> opstack;
std::vector<Token> output;
output.reserve(infix.size());
for (auto token : infix) {
if (std::holds_alternative<int>(token)) {
output.push_back(token);
} else {
// Handle operator
auto op = std::get<Operator>(token);
if (op == LeftParens) {
opstack.push(op);
} else if (op == RightParens) {
while (opstack.top() != LeftParens) {
output.push_back(opstack.top());
opstack.pop();
}
// Discard LeftParens
opstack.pop();
} else {
while (!opstack.empty() && opstack.top() != LeftParens &&
precedence(opstack.top()) >= precedence(op)) {
output.push_back(opstack.top());
opstack.pop();
}
opstack.push(op);
}
}
}
// Push remaining operators to output
while (!opstack.empty()) {
output.push_back(opstack.top());
opstack.pop();
}
return output;
}
long long compute_rpn(const std::vector<Token> &rpn) {
std::stack<long long> num_stack;
for (auto token : rpn) {
if (std::holds_alternative<int>(token)) {
num_stack.push(std::get<int>(token));
} else {
auto y = num_stack.top();
num_stack.pop();
auto x = num_stack.top();
num_stack.pop();
long long result;
switch (std::get<Operator>(token)) {
case Add:
result = x + y;
break;
case Sub:
result = x - y;
break;
case Mul:
result = x * y;
break;
case Div:
result = x / y;
break;
default:
break;
}
num_stack.push(result);
}
}
return num_stack.top();
}
int main() {
std::ifstream is("evaluare.in");
std::ofstream os("evaluare.out");
std::string infix;
std::getline(is, infix);
auto infix_tokens = tokenize(infix);
auto rpn_tokens = convert_to_rpn(infix_tokens);
os << compute_rpn(rpn_tokens) << '\n';
is.close();
os.close();
return 0;
}