diff --git a/core-java-modules/core-java-lang-operators-2/src/main/java/com/baeldung/infixpostfix/InfixToPostFixExpressionConversion.java b/core-java-modules/core-java-lang-operators-2/src/main/java/com/baeldung/infixpostfix/InfixToPostFixExpressionConversion.java new file mode 100644 index 000000000000..f18b6b194349 --- /dev/null +++ b/core-java-modules/core-java-lang-operators-2/src/main/java/com/baeldung/infixpostfix/InfixToPostFixExpressionConversion.java @@ -0,0 +1,67 @@ +package com.baeldung.infixpostfix; + +import java.util.Stack; + +public class InfixToPostFixExpressionConversion { + + private int getPrecedenceScore(char ch) { + switch (ch) { + case '^': + return 3; + + case '*': + case '/': + return 2; + + case '+': + case '-': + return 1; + } + return -1; + } + + private boolean isOperand(char ch) { + return (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'); + } + + private char associativity(char ch) { + if (ch == '^') + return 'R'; + return 'L'; + } + + public String infixToPostfix(String infix) { + StringBuilder result = new StringBuilder(); + Stack stack = new Stack<>(); + + for (int i = 0; i < infix.length(); i++) { + char ch = infix.charAt(i); + + if (isOperand(ch)) { + result.append(ch); + } else if (ch == '(') { + stack.push(ch); + } else if (ch == ')') { + while (!stack.isEmpty() && stack.peek() != '(') { + result.append(stack.pop()); + } + stack.pop(); + } else { + while (!stack.isEmpty() && (operatorPrecedenceCondition(infix, i, stack))) { + result.append(stack.pop()); + } + stack.push(ch); + } + } + + while (!stack.isEmpty()) { + result.append(stack.pop()); + } + + return result.toString(); + } + + private boolean operatorPrecedenceCondition(String infix, int i, Stack stack) { + return getPrecedenceScore(infix.charAt(i)) < getPrecedenceScore(stack.peek()) || getPrecedenceScore(infix.charAt(i)) == getPrecedenceScore(stack.peek()) && associativity(infix.charAt(i)) == 'L'; + } +} diff --git a/core-java-modules/core-java-lang-operators-2/src/test/java/com/baeldung/infixpostfix/InfixToPostfixExpressionUnitTest.java b/core-java-modules/core-java-lang-operators-2/src/test/java/com/baeldung/infixpostfix/InfixToPostfixExpressionUnitTest.java new file mode 100644 index 000000000000..f5b089883b25 --- /dev/null +++ b/core-java-modules/core-java-lang-operators-2/src/test/java/com/baeldung/infixpostfix/InfixToPostfixExpressionUnitTest.java @@ -0,0 +1,37 @@ +package com.baeldung.infixpostfix; + +import org.junit.Test; +import org.junit.jupiter.api.Assertions; + +public class InfixToPostfixExpressionUnitTest { + + @Test + public void givenSimpleOp_whenNoParenthesis_thenProduceValidPostfix() { + String infix = "a+b*c-d"; + String postfix = "abc*+d-"; + + InfixToPostFixExpressionConversion obj = new InfixToPostFixExpressionConversion(); + + Assertions.assertEquals(postfix, obj.infixToPostfix(infix)); + } + + @Test + public void givenSimpleOp_whenWithParenthesis_thenProduceValidPostfix() { + String infix = "(a+b)*(c-d)"; + String postfix = "ab+cd-*"; + + InfixToPostFixExpressionConversion obj = new InfixToPostFixExpressionConversion(); + + Assertions.assertEquals(postfix, obj.infixToPostfix(infix)); + } + + @Test + public void givenComplexOp_whenInputIsInfix_thenProduceValidPostfix() { + String infix = "a^b*(c^d-e)^(f+g*h)-i"; + String postfix = "ab^cd^e-fgh*+^*i-"; + + InfixToPostFixExpressionConversion obj = new InfixToPostFixExpressionConversion(); + + Assertions.assertEquals(postfix, obj.infixToPostfix(infix)); + } +}