Вычисление выражений стеком

Постфиксная (обратная польская) запись — это выражение, где операция стоит после своих аргументов. Вместо (8 + 9) * (1 - 7) пишут:

8 9 + 1 7 - *

Скобок нет и не нужно: порядок операций однозначно задан самой записью.

Алгоритм

Идём по токенам слева направо и держим стек чисел.

• Число — кладём в стек.
• Операция — снимаем два верхних числа, применяем, результат кладём обратно.

На примере: 8 и 9 ложатся в стек; + снимает их и кладёт 17; 1 и 7 ложатся; - снимает и кладёт $-6$; * снимает 17 и $-6$ и кладёт $-102$.

bool evalRPN(const vector<string>& tok, long long& res) {
    vector<long long> st;
    for (const string& t : tok) {
        if (t == "+" || t == "-" || t == "*") {
            if (st.size() < 2) return false;      // не хватило аргументов
            long long b = st.back(); st.pop_back();
            long long a = st.back(); st.pop_back();
            st.push_back(t == "+" ? a + b : t == "-" ? a - b : a * b);
        } else {
            st.push_back(stoll(t));
        }
    }
    if (st.size() != 1) return false;             // осталось лишнее
    res = st[0];
    return true;
}

Один проход, $O(n)$.

Порядок аргументов

Единственное место, где легко ошибиться. Первым снимается правый аргумент:

long long b = st.back(); st.pop_back();   // правый
long long a = st.back(); st.pop_back();   // левый

Для + и * разницы нет, для - и деления — есть. Запись 1 7 - означает $1 - 7 = -6$, а не $7 - 1$.

Проверка корректности достаётся даром

Запись некорректна ровно в двух случаях, и оба ловятся тем же проходом:

1. В стеке меньше двух чисел в момент операции — аргументов не хватило.
2. В конце в стеке не одно число — числа остались без применения.

Никакой отдельной валидации писать не нужно.

Проверено: на 200 000 случайных строк из чисел и знаков стековый разбор совпал с независимым рекурсивным разбором справа налево — и по вердикту о корректности, и по значению. Корректными оказались 20 889 строк, некорректными 179 111.

Почему стек, а не рекурсия

Рекурсивный разбор тоже работает: читаем токены справа налево, встретив операцию — рекурсивно разбираем два аргумента.

Но это тот же стек, только системный. Стек вызовов конечен (подробности), а vector растёт до предела памяти. На длинной записи рекурсия падает, цикл — нет.

Это общее правило: если алгоритм и так укладывается в один проход со стеком, системный стек не нужен.

Родственные постановки

Проверка скобочной последовательности. Открывающие скобки кладём в стек, закрывающая должна совпасть по типу с вершиной. В конце стек обязан быть пуст. Разбирается отдельно.

Инфиксная запись со скобками. Классический алгоритм — сортировочная станция: два стека, один для чисел, второй для операций; операция выталкивается, когда встречена операция не большего приоритета. Постфиксная запись — как раз то, что этот алгоритм производит.

Стек с минимумом. Если поверх вычисления нужен ещё и минимум по стеку, он добавляется бесплатно.