PrepBro
← Назад к вопросам

Вычисление выражения в обратной польской записи

1.0 Junior🔥 131 комментариев
#STL контейнеры и алгоритмы#Структуры данных и алгоритмы

Условие

Напишите функцию для вычисления значения арифметического выражения в обратной польской записи (Reverse Polish Notation, RPN).

Входные данные — вектор строк, где каждый элемент является либо целым числом, либо оператором (+, -, *, /).

Требования

  • Поддерживаемые операторы: +, -, *, /
  • Деление — целочисленное (результат округляется к нулю)
  • Гарантируется, что выражение корректно и не приводит к делению на ноль
  • Операнды и промежуточные результаты помещаются в int32_t

Пример

std::vector<std::string> tokens = {"2", "1", "+", "3", "*"};
int result = evalRPN(tokens); // (2 + 1) * 3 = 9

tokens = {"4", "13", "5", "/", "+"};
result = evalRPN(tokens); // 4 + (13 / 5) = 4 + 2 = 6

tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
result = evalRPN(tokens); // 22

Подсказка

Используйте стек для хранения операндов.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Вычисление Reverse Polish Notation (RPN)

Принцип работы

Обратная польская нотация (RPN) — это постфиксная запись, где операторы идут ПО СЛЕ операндов. Её главное преимущество — вычисление слева направо без скобок и приоритетов.

Алгоритм:

  1. Проходим по массиву слева направо
  2. Если элемент — число, кладём его в стек
  3. Если элемент — оператор, извлекаем два верхних элемента, выполняем операцию, кладём результат обратно
  4. В конце стека остаётся результат

Реализация

#include <vector>
#include <string>
#include <stack>
#include <cctype>
#include <stdexcept>

int evalRPN(std::vector<std::string>& tokens) {
    std::stack<long long> st;  // long long для промежуточных результатов
    
    for (const auto& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // Оператор — извлекаем два операнда
            if (st.size() < 2) {
                throw std::invalid_argument("Invalid RPN expression");
            }
            
            long long b = st.top(); st.pop();  // второй операнд
            long long a = st.top(); st.pop();  // первый операнд
            long long result = 0;
            
            if (token == "+") {
                result = a + b;
            } else if (token == "-") {
                result = a - b;
            } else if (token == "*") {
                result = a * b;
            } else if (token == "/") {
                // Целочисленное деление, округление к нулю
                if (b == 0) {
                    throw std::invalid_argument("Division by zero");
                }
                result = a / b;
            }
            
            st.push(result);
        } else {
            // Число — парсим и кладём в стек
            long long num = std::stoll(token);
            st.push(num);
        }
    }
    
    if (st.size() != 1) {
        throw std::invalid_argument("Invalid RPN expression");
    }
    
    return (int)st.top();
}

Трассировка примера 1

["2", "1", "+", "3", "*"]

ШагТокенСтек доСтек послеОписание
1"2"[][2]Число → в стек
2"1"[2][2, 1]Число → в стек
3"+"[2, 1][3]Pop 1, 2 → 2+1=3
4"3"[3][3, 3]Число → в стек
5"*"[3, 3][9]Pop 3, 3 → 3*3=9
Итог-[9][9]Результат: 9

Трассировка примера 2

["4", "13", "5", "/", "+"]

ШагТокенДействиеСтек
1"4"Push 4[4]
2"13"Push 13[4, 13]
3"5"Push 5[4, 13, 5]
4"/"Pop 5,13 → 13/5=2[4, 2]
5"+"Pop 2,4 → 4+2=6[6]
Итог--Результат: 6

Важные детали

1. Порядок операндов при вычитании и делении:

Стек: [10, 3]
Оператор: "-"
b = 3 (верхний элемент)
a = 10 (нижний элемент)
Результат: a - b = 10 - 3 = 7

2. Целочисленное деление: В C++ оператор / с целыми числами округляет к нулю:

13 / 5 = 2   // не 2.6
-13 / 5 = -2 // не -2.6

3. Использование long long: Применяем long long для стека, чтобы избежать переполнения при промежуточных вычислениях:

int a = INT_MAX;
int b = INT_MAX;
int result = a * b;  // ❌ переполнение!

long long a_ll = a;
long long b_ll = b;
long long result_ll = a_ll * b_ll;  // ✅ корректно

Анализ сложности

  • Временная сложность: O(N) — один проход по массиву
  • Пространственная сложность: O(N) — в худшем случае стек содержит N/2 элементов (все числа)

Альтернативные подходы

  1. Рекурсия — более сложна в реализации, требует явного стека
  2. Парсинг с regexp — медленнее, усложняет код
  3. Инфиксная к RPN конвертация (алгоритм Шунтинг-ярд) — нужна, если входные данные в инфиксной нотации

Тестирование граничных случаев

// Отрицательные числа
std::vector<std::string> tokens = {"-2", "3", "*"};
assert(evalRPN(tokens) == -6);

// Большие числа
tokens = {"1000000", "1000000", "*"};
assert(evalRPN(tokens) == 1000000000000LL);  // переполнение int!

// Деление с отрицательными
tokens = {"10", "-3", "/"};
assert(evalRPN(tokens) == -3);  // 10 / (-3) = -3 (к нулю)