Cod sursa(job #2916501)

Utilizator raul41917raul rotar raul41917 Data 30 iulie 2022 10:43:06
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.55 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fi("evaluare.in");
ofstream fo("evaluare.out");
///Evaluarea unei expresii
///Fie o expresie avand operatori , operanzi si paranteze
///Se cere sa calculezi valoarea expresiei
///Pentru a merge mai departe cu problema este necesar urmatorul concept
///Forma poloneza : este o modalitatte de a scrie o ecuatie in cadrul careia nu este nevoie de paranteze pentru a cunoaste ordinea in care
///se efectueaza operatiile corespunzatoare
///Daca pentru om este mai usoara citirea unei expresii de tip INFIX in care operatorii se gasesc intre operanzi , in cadrul prefix sau postfix , operatorul
///se gaseste inaintea/dupa cei doi operanzi
///Algoritmul de rezolvare - se folosesc doua cozi - una pentru valori , una pentru operatori
///Cat timp nu exista elemente in string avem:
///daca elementul citit este un numar atunci il introducem in stack
///daca avem o paranteza dreapta o introducem in stack
///daca avem o parateza stanga :
///scoatem ultimele doua valori din stiva
///scoatem ultmul operator din stiva operatorilor
///facem operatia si introducem in stiva de valori rezultatul
///se face acest preocedeu pana cand intalnim o paranteza dreapta sau stiva operatorilor devine goala
///daca in schimb avem un operator
///cat timp operatorul din varful stivei are precedenta mai mare decat operatorul care se cauta atunci doua valori din stiva valori si se opereaza
///se introduce in stiva operatorul
///la final daca exista in stiva operatori elemente se realizeaza acelasi procedeu
string s;
stack <int>val,op;
int precedence(char sign)
{
    if(sign=='+' || sign=='-')
        return 1;
    if(sign=='*' || sign=='/')
        return 2;
    return 0;
}
int calculEfectiv(int a,int b,char semn)
{
    if(semn=='+')
        return a+b;
    else if(semn=='-')
        return a-b;
    else if(semn=='*')
        return a*b;
    else
        return a/b;
}
int calcul(string s)
{
    int index=0;
    while(index<s.length())
    {
        if(s[index]==' ')
            continue;
        if(s[index]>='0' && s[index]<='9')
        {
            int numar=0;
            while(s[index]>='0' && s[index]<='9')
            {
                numar=numar*10+(s[index]-'0');
                index++;
            }
            val.push(numar);
            index--;
        }else if(s[index]=='(')
            op.push(s[index]);
        else if(s[index]==')')
        {
            while(!op.empty() && op.top()!='(')
            {
                int a=val.top();
                val.pop();
                int b=val.top();
                val.pop();
                char semn=op.top();
                op.pop();
                int rez=calculEfectiv(b,a,semn);
                val.push(rez);
            }
            op.pop();
        }else
        {
            while(!op.empty() && precedence(op.top())>=precedence(s[index]))
            {
                int a=val.top();
                val.pop();
                int b=val.top();
                val.pop();
                int rez=calculEfectiv(b,a,op.top());
                val.push(rez);
                op.pop();
            }
            op.push(s[index]);
        }
        index++;
    }
    while(!op.empty())
    {
        int a=val.top();
        val.pop();
        int b=val.top();
        val.pop();
        int rez=calculEfectiv(b,a,op.top());
        op.pop();
        val.push(rez);
    }
    return val.top();
}
int main()
{
    fi>>s;
    fo<<calcul(s);
    return 0;
}