Pagini recente » Cod sursa (job #1945993) | Cod sursa (job #1121070) | Cod sursa (job #618732) | Cod sursa (job #2340513) | Cod sursa (job #3349924)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
int precedence(int c){
if(c == '^') return 3;
if(c == '*' || c == '/') return 2;
if(c == '+' || c == '-') return 1;
return -1;
}
bool isRightAssociative(char c){
return c == '^';
}
bool isOperator(char c){
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
int floordiv(int a, int b){
if(a * b < 0 && a % b != 0){
return (a/b)-1;
}
return a/b;
}
vector<string> infixToPrefix(string &sir){
vector<string> res;
stack<char> st;
int n = sir.size();
for(int i = n-1; i>=0; i--){
char c = sir[i];
if(isdigit(c)){
int j = i;
while(j >= 0 && isdigit(sir[j]))j--;
string num = sir.substr(j+1, i-j);
res.push_back(num);
i = j+1;
}
else if(c == ')'){
st.push(c);
}
else if(c == '('){
while(!st.empty() && st.top() != ')'){
string stChr = string(1, st.top());
res.push_back(stChr);
st.pop();
}
if(!st.empty()){
st.pop();
}
}
else if(isOperator(c))
{
while(!st.empty() && isOperator(st.top()) && (precedence(c) < precedence(st.top()) || precedence(c) == precedence(st.top()) && isRightAssociative(c))){
string stChr = string(1, st.top());
res.push_back(stChr);
st.pop();
}
st.push(c);
}
}
while(!st.empty()){
string stChr = string(1, st.top());
res.push_back(stChr);
st.pop();
}
reverse(res.begin(), res.end());
return res;
}
int evaluatePolish(vector<string> &polish){
int n = polish.size();
stack<int> st;
for(int i = n-1; i>=0; i--){
string s = polish[i];
if(isdigit(s[0])){
st.push(stoi(s));
}
else{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
if(s == "+") st.push(a+b);
else if(s == "-") st.push(a-b);
else if(s == "*") st.push(a*b);
else if(s == "/") st.push(floordiv(a, b));
else if(s == "^") st.push(pow(a,b));
}
}
return st.top();
}
int main()
{
string sir;
fin >> sir;
vector<string> polish = infixToPrefix(sir);
// for(string s : polish) cout << s << ' ';
fout << evaluatePolish(polish);
return 0;
}