Cod sursa(job #1974122)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 26 aprilie 2017 21:24:13
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");

const int strMax = 1e5 + 5;

int N,nrPost;
char str[strMax],prio[256];
// str - sirul din input
// prio[c] = precaderea operatorului c ( ( , ) , * , / , + , - )
//           (cei cu precadere mai mare se executa primii)

struct elem {
    int nr;
    char c;
    elem(int _nr = 0,int _c = '\0') {
        nr = _nr;
        c = _c;
    }
}postfix[strMax];
// postfix[i] = un element in expresia postfix obtinuta
// care poate fi un numar (retinut in campul nr) sau un operand (retinut in campul c)

int getNumber(int&);
// getNumber return-eaza numarul curent din sirul din input

int main() {
    in>>(str+2);

    // se adauga paranteze la inceput si sfarsit pentru
    // a nu fi nevoie sa se verifice daca stiva este goala
    str[1] = '(';
    N = strlen(str+1);
    str[N += 1] = ')';

    prio['('] = prio[')'] = 1;
    prio['+'] = prio['-'] = 2;
    prio['*'] = prio['/'] = 3;

    // se transforma expresia cu notatie infix intr-o expresie
    // cu notatie postfix (forma poloneza postfixata)
    // folosind shunting-yard algorithm
    int i = 1;
    stack<char> st;
    // st = stiva in care se insereaza operatorii

    while (i <= N) {
        if ('0' <= str[i] && str[i] <= '9') {
            int nr = getNumber(i);
            postfix[++nrPost] = elem(nr,'\0');
        }
        else if (str[i] == '(') {
            st.push('(');
        }
        else if (str[i] == ')') {
            while (st.top() != '(') {
                postfix[++nrPost] = elem(0,st.top());
                st.pop();
            }
            st.pop();
        }
        else {
            if (prio[str[i]] > prio[st.top()]) {
                st.push(str[i]);
            }
            else {
                while (prio[st.top()] >= prio[str[i]]) {
                    postfix[++nrPost] = elem(0,st.top());
                    st.pop();
                }
                st.push(str[i]);
            }
        }
        ++i;
    }

    stack<int> aux;
    // se evalueaza expresia postfix obtinuta
    // aux = stiva in care se retin operanzii

    for (int i=1;i<=nrPost;++i) {
        if (postfix[i].c == '\0') {
            aux.push(postfix[i].nr);
        }
        else {
            int nr1,nr2,res = 0;
            nr1 = aux.top(); aux.pop();
            nr2 = aux.top(); aux.pop();
            char op = postfix[i].c;
            switch (op) {
                case '+': {
                    res = nr2 + nr1;
                    break;
                }
                case '-': {
                    res = nr2 - nr1;
                    break;
                }
                case '*': {
                    res = nr2 * nr1;
                    break;
                }
                case '/': {
                    res = nr2 / nr1;
                }
            }

            aux.push(res);
        }
    }
    out<<aux.top()<<'\n';

    in.close();out.close();
    return 0;
}

int getNumber(int& i) {
    int nr = 0;
    while ('0' <= str[i] && str[i] <= '9') {
        nr = nr * 10 + (str[i]-'0');
        ++i;
    }
    --i;
    return nr;
}