Clasa a XI-a · Alocare dinamică: liste, stive, coziRead in English
Evaluarea unei expresii în formă poloneză postfixată în C++
În engleză: Evaluating an expression in postfix (reverse Polish) notation
Ideea
În forma postfixată operatorul se scrie după operanzi: (3 + 4) * 2 devine 3 4 + 2 *, iar parantezele nu mai sunt necesare. Citim elementele pe rând: un număr se pune pe stivă; la un operator scoatem doi operanzi (întâi pe cel din dreapta, apoi pe cel din stânga), calculăm și punem rezultatul înapoi. La final pe stivă rămâne valoarea expresiei. Operatori: + - * / (împărțirea este întreagă). Elementele sunt despărțite prin spații.
Descrierea în engleză
In postfix notation the operator is written after its operands: (3 + 4) * 2 becomes 3 4 + 2 *, and parentheses are no longer needed. We read the elements one by one: a number is pushed onto the stack; for an operator we pop two operands (first the right one, then the left one), compute and push the result back. At the end the stack holds the value of the expression. Operators: + - * / (division is integer division). The elements are separated by spaces.
- Complexitate
- O(n), unde n este numărul de elemente ale expresiei
- Clasa
- Clasa a XI-a (Grade 11)
Exemple
Intrare
3 4 + 2 *
Ieșire așteptată
14
Intrare
5 1 2 + 4 * + 3 -
Ieșire așteptată
14
Codul C++
Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.
/*
* Titlu: Evaluarea unei expresii în formă poloneză postfixată
* Clasa: 11
* Capitol: Alocare dinamică: liste, stive, cozi
* Descriere: În forma postfixată operatorul se scrie după operanzi: (3 + 4) * 2 devine
* 3 4 + 2 *, iar parantezele nu mai sunt necesare. Citim elementele pe rând:
* un număr se pune pe stivă; la un operator scoatem doi operanzi (întâi pe cel
* din dreapta, apoi pe cel din stânga), calculăm și punem rezultatul înapoi.
* La final pe stivă rămâne valoarea expresiei. Operatori: + - * / (împărțirea
* este întreagă). Elementele sunt despărțite prin spații.
* Complexitate: O(n), unde n este numărul de elemente ale expresiei
*
* Exemplu
* Intrare: 3 4 + 2 *
* Ieșire: 14
*
* Exemplu
* Intrare: 5 1 2 + 4 * + 3 -
* Ieșire: 14
*/
#include <iostream>
#include <string>
using namespace std;
long long st[10005];
int vf = 0;
int main()
{
string element;
while (cin >> element)
{
bool operatorul = element.size() == 1 &&
(element[0] == '+' || element[0] == '-' || element[0] == '*' || element[0] == '/');
if (!operatorul)
{
st[++vf] = stoll(element);
continue;
}
long long dreapta = st[vf--];
long long stanga = st[vf--];
long long rezultat;
if (element[0] == '+')
{
rezultat = stanga + dreapta;
}
else if (element[0] == '-')
{
rezultat = stanga - dreapta;
}
else if (element[0] == '*')
{
rezultat = stanga * dreapta;
}
else
{
rezultat = stanga / dreapta;
}
st[++vf] = rezultat;
}
cout << st[vf] << '\n';
return 0;
}
Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.