Grade 11 · Dynamic allocation: lists, stacks, queuesCitește în română

Evaluating an expression in postfix (reverse Polish) notation

Original: Evaluarea unei expresii în formă poloneză postfixată

O(n)C++1764 lines2 examples

The idea

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.

Original description (Romanian)

Î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.

Complexity
O(n), where n is the number of elements in the expression
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

3 4 + 2 *

Expected output

14
Example 2

Input

5 1 2 + 4 * + 3 -

Expected output

14

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

forma-poloneza-postfixata.cpp
/*
 * 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;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.