Cod sursa(job #3349923)

Utilizator eric_dragosDragos Eric eric_dragos Data 3 aprilie 2026 16:26:23
Problema Evaluarea unei expresii Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#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(isalnum(c)){
            int j = i;
            while(j >= 0 && isalnum(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]) || s.size() > 1 && 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);    
    fout << evaluatePolish(polish);
    return 0;
}