InfixToPrefix.java

packagecom.thealgorithms.stacks;

importjava.util.Stack;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;

publicfinalclassInfixToPrefix {
privateInfixToPrefix() {
 }

/**
 * Convert an infix expression to a prefix expression using stack.
 *
 * @param infixExpression the infix expression to convert
 * @return the prefix expression
 * @throws IllegalArgumentException if the infix expression has unbalanced brackets
 * @throws NullPointerException if the infix expression is null
 */
publicstaticStringinfix2Prefix(StringinfixExpression) throwsIllegalArgumentException {
if (infixExpression == null) {
thrownewNullPointerException("Input expression cannot be null.");
 }
infixExpression = infixExpression.trim();
if (infixExpression.isEmpty()) {
return"";
 }
if (!BalancedBrackets.isBalanced(filterBrackets(infixExpression))) {
thrownewIllegalArgumentException("Invalid expression: unbalanced brackets.");
 }

StringBuilderoutput = newStringBuilder();
Stack<Character> stack = newStack<>();
// Reverse the infix expression for prefix conversion
StringreversedInfix = newStringBuilder(infixExpression).reverse().toString();
for (charelement : reversedInfix.toCharArray()) {
if (Character.isLetterOrDigit(element)) {
output.append(element);
 } elseif (element == ')') {
stack.push(element);
 } elseif (element == '(') {
while (!stack.isEmpty() && stack.peek() != ')') {
output.append(stack.pop());
 }
stack.pop();
 } else {
while (!stack.isEmpty() && precedence(element) < precedence(stack.peek())) {
output.append(stack.pop());
 }
stack.push(element);
 }
 }
while (!stack.isEmpty()) {
output.append(stack.pop());
 }

// Reverse the result to get the prefix expression
returnoutput.reverse().toString();
 }

/**
 * Determines the precedence of an operator.
 *
 * @param operator the operator whose precedence is to be determined
 * @return the precedence of the operator
 */
privatestaticintprecedence(charoperator) {
switch (operator) {
case'+':
case'-':
return0;
case'*':
case'/':
return1;
case'^':
return2;
default:
return -1;
 }
 }

/**
 * Filters out all characters from the input string except brackets.
 *
 * @param input the input string to filter
 * @return a string containing only brackets from the input string
 */
privatestaticStringfilterBrackets(Stringinput) {
Patternpattern = Pattern.compile("[^(){}\\[\\]<>]");
Matchermatcher = pattern.matcher(input);
returnmatcher.replaceAll("");
 }
}