PrefixToInfix.java

packagecom.thealgorithms.stacks;

importjava.util.Stack;

/**
 * Converts a prefix expression to an infix expression using a stack.
 *
 * The input prefix expression should consist of
 * valid operands (letters or digits) and operators (+, -, *, /, ^).
 * Parentheses are not required in the prefix string.
 */
publicfinalclassPrefixToInfix {
privatePrefixToInfix() {
 }

/**
 * Determines if a given character is a valid arithmetic operator.
 *
 * @param token the character to check
 * @return true if the character is an operator, false otherwise
 */
publicstaticbooleanisOperator(chartoken) {
returntoken == '+' || token == '-' || token == '/' || token == '*' || token == '^';
 }

/**
 * Converts a valid prefix expression to an infix expression.
 *
 * @param prefix the prefix expression to convert
 * @return the equivalent infix expression
 * @throws NullPointerException if the prefix expression is null
 */
publicstaticStringgetPrefixToInfix(Stringprefix) {
if (prefix == null) {
thrownewNullPointerException("Null prefix expression");
 }
if (prefix.isEmpty()) {
return"";
 }

Stack<String> stack = newStack<>();

// Iterate over the prefix expression from right to left
for (inti = prefix.length() - 1; i >= 0; i--) {
chartoken = prefix.charAt(i);

if (isOperator(token)) {
// Pop two operands from stack
StringoperandA = stack.pop();
StringoperandB = stack.pop();

// Form the infix expression with parentheses
Stringinfix = "(" + operandA + token + operandB + ")";

// Push the resulting infix expression back onto the stack
stack.push(infix);
 } else {
// Push operand onto stack
stack.push(Character.toString(token));
 }
 }

if (stack.size() != 1) {
thrownewArithmeticException("Malformed prefix expression");
 }

returnstack.pop(); // final element on the stack is the full infix expression
 }
}