Skip to content

refactor: Improve readability and code clarity in InfixToPostfix #6362

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 4 commits into
base: master
Choose a base branch
from
Open
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
100 changes: 71 additions & 29 deletions src/main/java/com/thealgorithms/stacks/InfixToPostfix.java
Original file line number Diff line number Diff line change
Expand Up @@ -4,54 +4,96 @@
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
* Utility class for converting an infix arithmetic expression
* into its equivalent postfix (Reverse Polish Notation) form.
* <p>
* This class provides a static method to perform the conversion,
* validating balanced brackets before processing.
* </p>
*/
public final class InfixToPostfix {

private InfixToPostfix() {
}

public static String infix2PostFix(String infixExpression) throws Exception {
/**
* Converts a given infix expression string to a postfix expression string.
* <p>
* The method first checks if the brackets in the input expression are balanced
* by calling {@code BalancedBrackets.isBalanced} on the filtered brackets.
* If the brackets are not balanced, it throws an IllegalArgumentException.
* </p>
* <p>
* Supported operators are: {@code +, -, *, /, ^}
* and operands can be letters or digits.
* </p>
*
* @param infixExpression the arithmetic expression in infix notation
* @return the equivalent postfix notation expression
* @throws IllegalArgumentException if the brackets in the expression are unbalanced
*/
public static String infix2PostFix(String infixExpression) {
if (!BalancedBrackets.isBalanced(filterBrackets(infixExpression))) {
throw new Exception("invalid expression");
throw new IllegalArgumentException("Invalid expression: unbalanced brackets.");
}

StringBuilder output = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (char element : infixExpression.toCharArray()) {
if (Character.isLetterOrDigit(element)) {
output.append(element);
} else if (element == '(') {
stack.push(element);
} else if (element == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
output.append(stack.pop());
Stack<Character> operatorStack = new Stack<>();

for (char token : infixExpression.toCharArray()) {
if (Character.isLetterOrDigit(token)) {
// Append operands (letters or digits) directly to output
output.append(token);
} else if (token == '(') {
// Push '(' to stack
operatorStack.push(token);
} else if (token == ')') {
// Pop and append until '(' is found
while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
output.append(operatorStack.pop());
}
stack.pop();
operatorStack.pop(); // Remove '(' from stack
} else {
while (!stack.isEmpty() && precedence(element) <= precedence(stack.peek())) {
output.append(stack.pop());
// Pop operators with higher or equal precedence and append them
while (!operatorStack.isEmpty() && precedence(token) <= precedence(operatorStack.peek())) {
output.append(operatorStack.pop());
}
stack.push(element);
operatorStack.push(token);
}
}
while (!stack.isEmpty()) {
output.append(stack.pop());

// Pop any remaining operators
while (!operatorStack.isEmpty()) {
output.append(operatorStack.pop());
}

return output.toString();
}

/**
* Returns the precedence level of the given operator.
*
* @param operator the operator character (e.g., '+', '-', '*', '/', '^')
* @return the precedence value: higher means higher precedence,
* or -1 if the character is not a recognized operator
*/
private static int precedence(char operator) {
switch (operator) {
case '+':
case '-':
return 0;
case '*':
case '/':
return 1;
case '^':
return 2;
default:
return -1;
}
return switch (operator) {
case '+', '-' -> 0;
case '*', '/' -> 1;
case '^' -> 2;
default -> -1;
};
}

/**
* Extracts only the bracket characters from the input string.
* Supports parentheses (), curly braces {}, square brackets [], and angle brackets &lt;&gt;.
*
* @param input the original expression string
* @return a string containing only bracket characters from the input
*/
private static String filterBrackets(String input) {
Pattern pattern = Pattern.compile("[^(){}\\[\\]<>]");
Matcher matcher = pattern.matcher(input);
Expand Down
Original file line number Diff line number Diff line change
Expand Up @@ -12,7 +12,7 @@ class InfixToPostfixTest {

@ParameterizedTest
@MethodSource("provideValidExpressions")
void testValidExpressions(String infix, String expectedPostfix) throws Exception {
void testValidExpressions(String infix, String expectedPostfix) {
assertEquals(expectedPostfix, InfixToPostfix.infix2PostFix(infix));
}

Expand All @@ -28,6 +28,6 @@ void testInvalidExpressions(String infix, String expectedMessage) {
}

private static Stream<Arguments> provideInvalidExpressions() {
return Stream.of(Arguments.of("((a+b)*c-d", "invalid expression"));
return Stream.of(Arguments.of("((a+b)*c-d", "Invalid expression: unbalanced brackets."));
}
}
Loading