Pagini recente » Cod sursa (job #1115931) | Cod sursa (job #2427411) | Cod sursa (job #1775990) | Cod sursa (job #2207875) | Cod sursa (job #3312543)
#include <bits/stdc++.h>
using namespace std;
// Infix expression (with (), +, -, *, /)
// |
// v
// Shunting-yard
// |
// v
// RPN (postfix form, unambiguous, no parentheses) OR expression tree
// |
// v
// Stack-based evaluation
// |
// v
// Final integer result
inline int precedence(char op) {
switch (op) {
case '+':
return 1;
case '-':
return 1;
case '*':
return 2;
case '/':
return 2;
default:
return 0;
}
}
int main() {
#ifndef LOCAL
freopen("evaluare.in", "r", stdin);
freopen("evaluare.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
string expr;
cin >> expr;
vector<string> rpxe;
stack<char> s;
for (std::size_t i = 0; i < expr.size(); ++i) {
if (!isspace(expr[i])) {
if (isdigit(expr[i])) {
std::string number;
for (; i < expr.size() && isdigit(expr[i]);) {
number.push_back(expr[i++]);
}
rpxe.push_back(number);
--i;
} else {
switch (expr[i]) {
case '(':
s.push(expr[i]);
break;
case ')':
for (; s.size() && s.top() != '(';) {
rpxe.push_back(string(1, s.top()));
s.pop();
}
s.pop();
break;
default:
for (; s.size() && precedence(s.top()) >= precedence(expr[i]);) {
rpxe.push_back(string(1, s.top()));
s.pop();
}
s.push(expr[i]);
}
}
}
}
for (; s.size();) {
rpxe.push_back(string(1, s.top()));
s.pop();
}
stack<int> p;
for (auto& subexpr : rpxe) {
if (subexpr == "+" || subexpr == "-" || subexpr == "*" || subexpr == "/") {
int b = p.top();
p.pop();
int a = p.top();
p.pop();
if (subexpr == "+") {
p.push(a + b);
} else if (subexpr == "-") {
p.push(a - b);
} else if (subexpr == "*") {
p.push(a * b);
} else if (subexpr == "/") {
p.push(a / b);
}
} else {
p.push(stoi(subexpr));
}
}
assert(p.size() == 1);
std::cout << p.top();
return 0;
}