src/main/java/com/thealgorithms/stacks/PostfixEvaluator.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/stacks/PostfixEvaluator.java

74 строки2 KB

Hardik Pawar

feat: Add `PostfixEvaluator` new algorithm with Junit tests (#5754)

13 окт 2024, 13:50

13 окт 2024, 13:50b0c8a8f

package com.thealgorithms.stacks;

import java.util.Set;
import java.util.Stack;

/**
 * Evaluate a postfix (Reverse Polish) expression using a stack.
 *
 * <p>Example: Expression "5 6 + 2 *" results in 22.
 * <p>Applications: Used in calculators and expression evaluation in compilers.
 *
 * @author Hardvan
 */
public final class PostfixEvaluator {
    private PostfixEvaluator() {
    }

    private static final Set<String> OPERATORS = Set.of("+", "-", "*", "/");

    /**
     * Evaluates the given postfix expression and returns the result.
     *
     * @param expression The postfix expression as a string with operands and operators separated by spaces.
     * @return The result of evaluating the postfix expression.
     * @throws IllegalArgumentException if the expression is invalid.
     */
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();

        for (String token : expression.split("\\s+")) {
            if (isOperator(token)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(applyOperator(token, operand1, operand2));
            } else {
                stack.push(Integer.valueOf(token));
            }
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid expression");
        }

        return stack.pop();
    }

    /**
     * Checks if the given token is an operator.
     *
     * @param token The token to check.
     * @return true if the token is an operator, false otherwise.
     */
    private static boolean isOperator(String token) {
        return OPERATORS.contains(token);
    }

    /**
     * Applies the given operator to the two operands.
     *
     * @param operator The operator to apply.
     * @param a The first operand.
     * @param b The second operand.
     * @return The result of applying the operator to the operands.
     */
    private static int applyOperator(String operator, int a, int b) {
        return switch (operator) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            case "/" -> a / b;
            default -> throw new IllegalArgumentException("Invalid operator");
        };
    }
}