Rezolvare completă PbInfo #3536 EvaluareExpresie

Cerința

Se consideră o expresie aritmetică formată din numere naturale și operatorii binari + (adunare), - (scădere), * (înmulțire), ^ (ridicare la putere). Să se determine forma postfixată corespunzătoare și să se calculeze valoarea expresiei.
Spunem că expresia este în formă infixată dacă fiecare operator binar este încadrat de cei doi operanzi ai săi. Aceasta este de fapt forma uzuală a expresiilor aritmetice.
Spunem că expresia este în formă postfixată dacă fiecare operator este poziționat după operanzii săi, respectând prioritatea și regula de asociere a operatorilor.
De exemplu, expresia aritmetică în formă infixată: 1*2+3^4 poate fi rescrisă în forma postfixată astfel:
1*2+3^4 → (parantezare) → ((1*2)+(3^4)) → (postfixare +) → ((1*2)(3^4)+) → (postfixare * și ^) → ((1 2 *)(3 4 ^) +) → (eliminare paranteze) → 1 2 * 3 4 ^ +
Valoarea expresiei date este 83.

Date de intrare

Fișierul de intrare evaluareexpresie.in conține pe un singur rând un șir de caractere ce reprezintă o expresie aritmetică corect construită ce poate conține numai operatorii binari +, -, *, ^, cu semnificațiile de mai sus, și operanzi constante numere naturale.

Date de ieșire

Fișierul de ieșire evaluareexpresie.out va conține pe prima linie un șir de caractere ce reprezintă forma postfixată a expresiei date, iar pe cel de-al doilea rând un număr natural ce reprezintă valoarea expresiei date. Pentru forma postfixată operanzii și operatorii vor fi separați cu câte un spațiu.

Restricții și precizări

  • Lungimea expresiei din fișierul de intrare va fi de cel mult 50 de caractere
  • Rezultatul final precum și rezultatele intermediare se vor încadra în tipul de date long long
  • Expresia este corectă și nu conține alte caractere în afară de cifre și operatorii +, -, *, ^

Exemplul 1:

evaluareexpresie.in

100-2*3^2

evaluareexpresie.out

100 2 3 2 ^ * -
82

Explicație

100-2*3^2 → (100-(2*(3^2))) → (100-(2*(3 2^))) → (100-(2(3 2^)*)) → (100(2(3 2^)*)-) → 100 2 3 2 ^ * -
Valoare expresiei este 82.

Exemplul 2:

evaluareexpresie.in

1+2+2^3^2

evaluareexpresie.out

1 2 + 2 3 ^ 2 ^ +
67

Explicație

1+2+2^3^2 → ((1+2)+((2^3)^2)) → ((1 2 +)+((2 3 ^)^2)) → ((1 2 +)+((2 3 ^) 2 ^)) → ((1 2 +)((2 3 ^) 2 ^) +) → 1 2 + 2 3 ^ 2 ^ +
Valoare expresiei este 67.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema EvaluareExpresie:

#include <bits/stdc++.h>
using namespace std;

ifstream in("evaluareexpresie.in");
ofstream out("evaluareexpresie.out");

#define MAX 51

int prec(string c)
{
    if (c == "^")
        return 3;
    if (c == "*")
        return 2;
    return 1;//(c == "+" || c == "-")
}

vector<string> CreateTokens(string text)
{
    vector<string> tokens;
    int i = 0;
    string m = "";
    while (text[i])
    {
        if (strchr("+-*^", text[i]))
        {
            tokens.push_back(m);
            tokens.push_back(string(1, text[i]));
            m = "";
        }
        else
            m += text[i];
        i++;
    }
    tokens.push_back(m);
    return tokens;
}

vector<string> infixToPostfix(vector<string> tokens)
{
    vector<string> output;
    stack<string> st;
    for (int i = 0; i < tokens.size(); i++)
    {
        if (!strchr("+*-^", tokens[i][0]))//operand
            output.push_back(tokens[i]);
        else {//operator
            while (!st.empty() && prec(tokens[i]) <= prec(st.top()))
            {
                string s = st.top();
                st.pop();
                output.push_back(s);
            }
            st.push(tokens[i]);
        }
    }
    while (!st.empty())
    {
        string s = st.top();
        st.pop();
        output.push_back(s);
    }
    return output;
}

long long int PostfixEval(vector<string> tokens)
{
    stack<long long int> nums;
    int len = tokens.size();

    for (int i = 0; i < len; i++) {
        if (strchr("+-*^", tokens[i][0])) //operator
        {
            long long int a = 0, b = 0;
            if (nums.size())
            {
                b = nums.top();
                nums.pop();
            }
            if (nums.size())
            {
                a = nums.top();
                nums.pop();
            }
            switch (tokens[i][0])
            {
                case '+': nums.push(a + b); break;
                case '-': nums.push(a - b); break;
                case '*': nums.push(a * b); break;
                case '^': nums.push(pow(a, b) + 0.5); break;
            }
        }
        else
            nums.push(stoll(tokens[i]));
    }
    if (nums.size())
        return nums.top();
    return 0;
}

int main()
{
    char exp[MAX];
    in.getline(exp, MAX);
    
    vector<string> tokens = CreateTokens(string(exp));
    vector<string> postfix = infixToPostfix(tokens);
    
    for (string i : postfix)
        out << i<<" ";
    out << "\n";
    
    out << PostfixEval(postfix);
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3536 EvaluareExpresie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3536 EvaluareExpresie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!