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

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

76 строк2 KB

Hardik Pawar

feat: Add `PrefixEvaluator` new algorithm with Junit tests (#5755)

13 окт 2024, 13:57

13 окт 2024, 13:57bae7f89

package com.thealgorithms.stacks;

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

/**
 * Evaluate a prefix (Polish) expression using a stack.
 *
 * <p>Example: Expression "+ * 2 3 4" results in 10.
 * <p>Applications: Useful for implementing compilers and interpreters.
 *
 * @author Hardvan
 */
public final class PrefixEvaluator {
    private PrefixEvaluator() {
    }

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

    /**
     * Evaluates the given prefix expression and returns the result.
     *
     * @param expression The prefix expression as a string with operands and operators separated by spaces.
     * @return The result of evaluating the prefix expression.
     * @throws IllegalArgumentException if the expression is invalid.
     */
    public static int evaluatePrefix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split("\\s+");

        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];
            if (isOperator(token)) {
                int operand1 = stack.pop();
                int operand2 = 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");
        };
    }
}