Обратная польская нотация (калькулятор)

Обратная польская нотация (калькулятор RPN)

Суть алгоритма

Обратная (постфиксная) польская нотация — это способ записи математических выражений, где операторы идут после операндов. Главное преимущество: не нужны скобки, и алгоритм вычисления очень простой благодаря Stack.

Как работает RPN

Обычная нотация (инфиксная):  (2 + 1) * 3 = 9
Постфиксная нотация:          2 1 + 3 *

Алгоритм:
1. Читаем 2 → push на stack → [2]
2. Читаем 1 → push на stack → [2, 1]
3. Читаем + → pop два операнда (1, 2), вычисляем 2 + 1 = 3, push → [3]
4. Читаем 3 → push на stack → [3, 3]
5. Читаем * → pop два операнда (3, 3), вычисляем 3 * 3 = 9, push → [9]
6. Результат: 9

Реализация

import java.util.*;

public class ReversePolishNotationCalculator {
    
    /**
     * Вычисляет выражение в обратной польской нотации
     * @param tokens массив токенов (числа и операторы)
     * @return результат вычисления
     * @throws IllegalArgumentException если выражение некорректно
     */
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            throw new IllegalArgumentException("Пустое выражение");
        }
        
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                // Если это оператор, pop два операнда
                if (stack.size() < 2) {
                    throw new IllegalArgumentException(
                        "Некорректное выражение: недостаточно операндов для " + token);
                }
                
                int b = stack.pop();  // второй операнд
                int a = stack.pop();  // первый операнд
                int result = applyOperator(token, a, b);
                stack.push(result);
            } else {
                // Если это число, push на stack
                try {
                    int num = Integer.parseInt(token);
                    stack.push(num);
                } catch (NumberFormatException e) {
                    throw new IllegalArgumentException("Некорректный токен: " + token);
                }
            }
        }
        
        // В конце должно остаться ровно одно число (результат)
        if (stack.size() != 1) {
            throw new IllegalArgumentException(
                "Некорректное выражение: слишком много операндов");
        }
        
        return stack.pop();
    }
    
    /**
     * Проверяет, является ли токен оператором
     */
    private boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || 
               "*".equals(token) || "/".equals(token);
    }
    
    /**
     * Применяет оператор к двум операндам
     */
    private int applyOperator(String operator, int a, int b) {
        switch (operator) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                if (b == 0) {
                    throw new ArithmeticException("Деление на ноль");
                }
                return a / b;  // целочисленное деление
            default:
                throw new IllegalArgumentException("Неизвестный оператор: " + operator);
        }
    }
}

Пошаговый пример

String[] tokens = {"2", "1", "+", "3", "*"};
// Выражение: 2 1 + 3 * = (2 + 1) * 3 = 9

Процесс:
Шаг 1: "2" → число → push(2) → stack = [2]
Шаг 2: "1" → число → push(1) → stack = [2, 1]
Шаг 3: "+" → оператор → pop(1), pop(2) → 2 + 1 = 3 → push(3) → stack = [3]
Шаг 4: "3" → число → push(3) → stack = [3, 3]
Шаг 5: "*" → оператор → pop(3), pop(3) → 3 * 3 = 9 → push(9) → stack = [9]

Результат: 9

Ещё примеры

Примеры вычисления:

1. "4 13 5 / +" = 6
   4 → [4]
   13 → [4, 13]
   5 → [4, 13, 5]
   / → pop(5, 13) → 13 / 5 = 2 → [4, 2]
   + → pop(2, 4) → 4 + 2 = 6 → [6]
   Ответ: 6

2. "15 7 1 1 + - / 3 * 2 1 1 + + -" = 5
   Это более сложное выражение, требует внимательного отслеживания stack

Обработка ошибок

public class ReversePolishNotationCalculator {
    
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            throw new IllegalArgumentException("Пустое выражение");
        }
        
        Stack<Integer> stack = new Stack<>();
        Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
        
        for (String token : tokens) {
            if (operators.contains(token)) {
                // Проверка: достаточно ли операндов
                if (stack.size() < 2) {
                    throw new IllegalArgumentException(
                        "Некорректное выражение: недостаточно операндов");
                }
                
                int b = stack.pop();
                int a = stack.pop();
                
                // Проверка деления на ноль
                if ("/".equals(token) && b == 0) {
                    throw new ArithmeticException("Деление на ноль");
                }
                
                int result = applyOperator(token, a, b);
                stack.push(result);
            } else {
                try {
                    int num = Integer.parseInt(token);
                    stack.push(num);
                } catch (NumberFormatException e) {
                    throw new IllegalArgumentException(
                        "Некорректный токен: " + token);
                }
            }
        }
        
        // Проверка: в конце должно быть ровно одно число
        if (stack.size() != 1) {
            throw new IllegalArgumentException(
                "Некорректное выражение: слишком много операндов");
        }
        
        return stack.pop();
    }
    
    private int applyOperator(String operator, int a, int b) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Неизвестный оператор");
        }
    }
}

Тесты

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class ReversePolishNotationCalculatorTest {
    private ReversePolishNotationCalculator calculator = 
        new ReversePolishNotationCalculator();
    
    @Test
    public void testSimpleAddition() {
        String[] tokens = {"2", "1", "+"};
        assertEquals(3, calculator.evalRPN(tokens));
    }
    
    @Test
    public void testComplexExpression1() {
        String[] tokens = {"2", "1", "+", "3", "*"};
        assertEquals(9, calculator.evalRPN(tokens));
    }
    
    @Test
    public void testComplexExpression2() {
        String[] tokens = {"4", "13", "5", "/", "+"};
        assertEquals(6, calculator.evalRPN(tokens));
    }
    
    @Test
    public void testDivision() {
        String[] tokens = {"10", "2", "/"};
        assertEquals(5, calculator.evalRPN(tokens));
    }
    
    @Test
    public void testNegativeNumbers() {
        String[] tokens = {"5", "-5", "+"};
        assertEquals(0, calculator.evalRPN(tokens));
    }
    
    @Test
    public void testDivisionByZero() {
        String[] tokens = {"5", "0", "/"};
        assertThrows(ArithmeticException.class, () -> calculator.evalRPN(tokens));
    }
    
    @Test
    public void testInsufficientOperands() {
        String[] tokens = {"2", "+"};
        assertThrows(IllegalArgumentException.class, () -> calculator.evalRPN(tokens));
    }
    
    @Test
    public void testTooManyOperands() {
        String[] tokens = {"2", "1", "3"};
        assertThrows(IllegalArgumentException.class, () -> calculator.evalRPN(tokens));
    }
    
    @Test
    public void testEmpty() {
        String[] tokens = {};
        assertThrows(IllegalArgumentException.class, () -> calculator.evalRPN(tokens));
    }
    
    @Test
    public void testNull() {
        assertThrows(IllegalArgumentException.class, () -> calculator.evalRPN(null));
    }
}

Временная сложность и пространство

Почему RPN удобнее инфиксной нотации?

Расширение: поддержка операций

private int applyOperator(String operator, int a, int b) {
    switch (operator) {
        case "+": return a + b;
        case "-": return a - b;
        case "*": return a * b;
        case "/": return a / b;
        case "%": return a % b;  // модуль
        case "^": return (int) Math.pow(a, b);  // степень
        default: throw new IllegalArgumentException("Неизвестный оператор");
    }
}

Вывод

Решение задачи RPN — это классический пример использования Stack. Ключевые моменты:

1. Алгоритм: для каждого токена — если число, то push; если оператор, то pop-apply-push
2. Ошибки: проверяй недостаток операндов, деление на ноль, лишние операнды
3. Stack: идеальная структура для этой задачи
4. Сложность: O(n) время и O(n) память

Этот алгоритм используется во многих калькуляторах и компиляторах для вычисления выражений!