Cod sursa(job #3151486)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 21 septembrie 2023 16:41:34
Problema Evaluarea unei expresii Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");
string s;
string polish;
unordered_map<char, int> ops;

string to_polish(string s) {
    string ans = "";
    stack<char> st;

    int n = s.length();
    int i = 0;
    string nr = "";
    while (i < n) {
        if (s[i] >= '0' && s[i] <= '9') {
            nr += s[i];
        } else {
            if (nr.length() > 0) {
                ans = ans + nr + " ";
                nr = "";
            }

            if (s[i] == '(') {
                st.push(s[i]);
            } else if (s[i] == ')') {
                while (!st.empty() && st.top() != '(') {
                    ans = ans + st.top() + " ";
                    st.pop();
                }
                st.pop();
            } else {
                while (!st.empty() && st.top() != '(' && ops[st.top()] >= ops[s[i]]) {
                    ans = ans + st.top() + " ";
                    st.pop();
                }

                st.push(s[i]);
            }
        }
        i++;
    }

    if (nr.length() > 0) {
        ans = ans + nr + " ";
        nr = "";
    }

    while (!st.empty()) {
        ans = ans + st.top() + " ";
        st.pop();
    }

    return ans;

}

int eval_polish(string s) {
    stack<int> st;

    int n = s.length();
    int i = 0;

    while (i < n) {
        if (s[i] == ' ') {
            i++;
            continue;
        }

        if (s[i] >= '0' && s[i] <= '9') {
            int nr = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                nr = nr * 10 + s[i] - '0';
                i++;
            }
            st.push(nr);
        } else {
            int x = st.top();
            st.pop();
            int y = st.top();
            st.pop();

            if (s[i] == '+') {
                st.push(x + y);
            } else if (s[i] == '-') {
                st.push(y - x);
            } else if (s[i] == '*') {
                st.push(x * y);
            } else {
                st.push(y / x);
            }
            i++;
        }
    }


    return st.top();

}

int main()
{
    in >> s;
    ops['+'] = 0;
    ops['-'] = 0;
    ops['*'] = 1;
    ops['/'] = 1;

    polish = to_polish(s);
    out << eval_polish(polish);

    return 0;
}