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

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

Это классическая задача на использование стека. Обратная польская запись (RPN, Postfix notation) — это запись, в которой операторы идут ПОСЛЕ операндов, что позволяет вычислять выражение слева направо без скобок.

Понимание RPN

Обычная запись (infix): (2 + 1) * 3 = 9 Обратная польская запись (postfix): 2 1 + 3 *

Как читать RPN:

• Слева направо ищем числа и операторы
• Оператор применяется к двум последним числам

2 1 + 3 *
↓ ↓ ↓ ↓ ↓
2: добавляем в стек → [2]
1: добавляем в стек → [2, 1]
+: берём два последних, складываем → [3]
3: добавляем в стек → [3, 3]
*: берём два последних, умножаем → [9]
Результат: 9

Решение 1: Стек (оптимальное)

Алгоритм:

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

def evaluate_rpn(tokens: list) -> int:
    stack = []
    operators = {'+', '-', '*', '/'}
    
    for token in tokens:
        if token in operators:
            # Извлекаем два операнда
            b = stack.pop()  # Второй операнд
            a = stack.pop()  # Первый операнд
            
            # Применяем оператор
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                # ВАЖНО: в Python -6 // 5 = -2, нам нужно -1
                # Используем int(a / b) для truncate к нулю
                result = int(a / b)
            
            stack.append(result)
        else:
            # Это число
            stack.append(int(token))
    
    return stack[0]

# Примеры
print(evaluate_rpn(["2", "1", "+", "3", "*"]))      # 9
print(evaluate_rpn(["4", "13", "5", "/", "+"]))    # 6
print(evaluate_rpn(["15", "7", "1", "1", "-", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"]))
# Сложный пример

*Как работает на "2 1 + 3 ":

"2": число → stack = [2]
"1": число → stack = [2, 1]
"+": оператор
  b = stack.pop() = 1
  a = stack.pop() = 2
  result = 2 + 1 = 3
  stack = [3]

"3": число → stack = [3, 3]

"*": оператор
  b = stack.pop() = 3
  a = stack.pop() = 3
  result = 3 * 3 = 9
  stack = [9]

Ответ: 9

Сложность:

• Время: O(n) — один проход
• Память: O(n) в худшем случае (все числа)

Решение 2: С использованием lambda и словаря

def evaluate_rpn_lambda(tokens: list) -> int:
    stack = []
    
    # Словарь операторов
    operations = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)
    }
    
    for token in tokens:
        if token in operations:
            b = stack.pop()
            a = stack.pop()
            result = operations[token](a, b)
            stack.append(result)
        else:
            stack.append(int(token))
    
    return stack[0]

print(evaluate_rpn_lambda(["2", "1", "+", "3", "*"]))  # 9

Плюсы: компактнее, легче добавить новые операторы

ВАЖНОЕ: Деление в Python

ВАЖНО ЗНАТЬ разницу между операторами деления!

# Проблема с //
print(6 // 2)       # 3 (правильно)
print(-6 // 2)      # -3 (правильно, floor division)
print(6 // 4)       # 1 (правильно)
print(-6 // 4)      # -2 (floor, НЕ truncate!)

# RPN требует truncate (отбрасывание дроби)
print(int(6 / 2))      # 3
print(int(-6 / 2))     # -3
print(int(6 / 4))      # 1
print(int(-6 / 4))     # -1 (верно для RPN)

# Правильный выбор для RPN:
result = int(a / b)  # Truncate к нулю

Решение 3: Полная версия с обработкой ошибок

def evaluate_rpn_safe(tokens: list) -> int:
    if not tokens:
        return 0
    
    stack = []
    operators = {'+', '-', '*', '/'}
    
    try:
        for token in tokens:
            if token in operators:
                if len(stack) < 2:
                    raise ValueError(f"Недостаточно операндов для {token}")
                
                b = stack.pop()
                a = stack.pop()
                
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                elif token == '/':
                    if b == 0:
                        raise ValueError("Деление на ноль")
                    stack.append(int(a / b))
            else:
                try:
                    stack.append(int(token))
                except ValueError:
                    raise ValueError(f"Некорректный токен: {token}")
        
        if len(stack) != 1:
            raise ValueError("Неправильное выражение")
        
        return stack[0]
    
    except Exception as e:
        print(f"Ошибка: {e}")
        return None

print(evaluate_rpn_safe(["2", "1", "+", "3", "*"]))      # 9
print(evaluate_rpn_safe(["2", "0", "/"]))                # Ошибка деления на ноль

Решение 4: С использованием operator module

import operator

def evaluate_rpn_operator(tokens: list) -> int:
    stack = []
    ops = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': lambda a, b: int(a / b)
    }
    
    for token in tokens:
        if token in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    
    return stack[0]

print(evaluate_rpn_operator(["2", "1", "+", "3", "*"]))  # 9

Тестовые случаи

def test_evaluate_rpn():
    # Базовые
    assert evaluate_rpn(["2", "1", "+"]) == 3
    assert evaluate_rpn(["3", "2", "-"]) == 1
    assert evaluate_rpn(["2", "3", "*"]) == 6
    assert evaluate_rpn(["6", "2", "/"]) == 3
    
    # Примеры из задания
    assert evaluate_rpn(["2", "1", "+", "3", "*"]) == 9
    assert evaluate_rpn(["4", "13", "5", "/", "+"]) == 6
    
    # Сложные
    assert evaluate_rpn(["10", "6", "/", "9", "+"]) == 10  # (10/6) + 9 = 1 + 9
    assert evaluate_rpn(["3", "4", "+", "2", "*", "7", "-"]) == 7  # ((3+4)*2)-7 = 14-7
    
    # Отрицательные
    assert evaluate_rpn(["2", "3", "-"]) == -1
    assert evaluate_rpn(["-2", "3", "*"]) == -6
    
    print("Все тесты пройдены!")

test_evaluate_rpn()

Преобразование Infix → Postfix (бонус)

Это обратная задача — преобразовать обычное выражение в RPN (используется алгоритм Shunting Yard):

def infix_to_postfix(infix):
    """Алгоритм Shunting Yard (Dijkstra)"""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    output = []
    operator_stack = []
    
    for token in infix.split():
        if token not in precedence and token not in '()':
            output.append(token)  # Число
        elif token == '(':
            operator_stack.append(token)
        elif token == ')':
            while operator_stack and operator_stack[-1] != '(':
                output.append(operator_stack.pop())
            operator_stack.pop()  # Удаляем '('
        else:  # Оператор
            while (operator_stack and 
                   operator_stack[-1] != '(' and
                   operator_stack[-1] in precedence and
                   precedence[operator_stack[-1]] >= precedence[token]):
                output.append(operator_stack.pop())
            operator_stack.append(token)
    
    while operator_stack:
        output.append(operator_stack.pop())
    
    return output

print(infix_to_postfix("2 + 1 * 3"))  # ['2', '1', '3', '*', '+']
print(infix_to_postfix("( 2 + 1 ) * 3"))  # ['2', '1', '+', '3', '*']

На собеседовании

Используй решение 1 или 2:

✅ Решение 1 (if-else):

• Самое явное и понятное
• Легко объяснить логику
• Стандартный подход

✅ Решение 2 (lambda + словарь):

• Более элегантное
• Легче расширять
• Показывает функциональное мышление

Обязательно обсудить:

1. Как работает стек
2. Почему int(a / b) вместо a // b
3. Сложность O(n)
4. Обработку ошибок (деление на 0)

Это часто встречается на собеседованиях и показывает глубокое понимание структур данных и алгоритмов.