Infix to postfix converter program java

In postfix notation, operator comes after operands. For example post fix from for

a+b => ab+

a-b => ab-

a*b => ab*

a/b => ab/

Following are some of the examples for infix to postfix.

1. a+b*c = a+bc*  (Since * has higher precedence over +)

     = abc*+

2. a*b+c = ab*+c (Since * has higher precedence over +)

     = ab*c+

3. (a+b)*c = (ab+)*c (Expression in () has higher precedence)

= ab+c*

4.a*b/c = ab*/c (*, / has same precedence, associativity rule used)

    = ab*c/

Following is the procedure to convert infix to postfix.

Step 1: Start reading expression character by character.

Step 2: If current character is an operator and stack is empty, push current character to stack.

b. If current character is an operator, then pop all operators from stack and add them to output, until you find a lower precedence operator than current operator.

c. Push current character to top of stack.

Step 3: If current character is ‘(‘, push it to top of stack

Step 4: If the current character is ‘)’, pop all characters from stack and add them to output until an ‘(‘ is encountered.

Step 5: If current character is not operator, or parenthesis then add it to output. Repeat steps 1 to 5, until all characters are consumed.

import java.util.LinkedList;
import java.util.Objects;

/* Works only for arithmetic operators */
public class InfixToPostfix {

 private LinkedList<Character> stack = new LinkedList<>();

 private static boolean isOperator(char ch) {
  return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%');
 }

 private static int getPrecedenxe(char ch) {
  switch (ch) {
  case '+':
  case '-':
   return 1;

  case '*':
  case '/':
  case '%':
   return 2;
  }
  return -1;
 }

 /**
  * Returns true, if ch1 has more or equal precedence than ch2. /, *, % has
  * more precedence than +, - /, *, % has same precedence +, - has same
  * precedence
  */
 private static boolean isGreaterPrecedence(char ch1, char ch2) {
  int preced1 = getPrecedenxe(ch1);
  int preced2 = getPrecedenxe(ch2);

  if (preced1 >= preced2)
   return true;
  return false;
 }

 private boolean isParanthesis(char ch) {
  return (ch == '(' || ch == ')');
 }

 public String getPostFixString(String expr) {
  Objects.nonNull(expr);
  StringBuilder builder = new StringBuilder("");

  for (int i = 0; i < expr.length(); i++) {
   char currentChar = expr.charAt(i);
   if (isOperator(currentChar)) {
    if (stack.isEmpty()) {
     stack.push(currentChar);
    } else if (isGreaterPrecedence(stack.peek(), currentChar)) {
     while (stack.peek() != null
       && isGreaterPrecedence(stack.peek(), currentChar))
      builder = builder.append(stack.pop());
     stack.push(currentChar);
    } else {
     stack.push(currentChar);
    }

   } else if (isParanthesis(currentChar)) {
    if (currentChar == '(') {
     stack.push(currentChar);
     continue;
    }

    while (stack.peek() != '(') {
     builder = builder.append(stack.pop());
    }
    stack.pop();
   } else {
    builder = builder.append(currentChar);
   }
  }

  while (!stack.isEmpty())
   builder = builder.append(stack.pop());

  return builder.toString();
 }
}

Following is the junit test case for above program.

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class InfixToPostfixTest {

 InfixToPostfix infixToPostfix = new InfixToPostfix();

 @Test
 public void test1() {
  assertEquals(infixToPostfix.getPostFixString("A*B+C"), "AB*C+");
  assertEquals(infixToPostfix.getPostFixString("A+B*C"), "ABC*+");
  assertEquals(infixToPostfix.getPostFixString("A*(B+C)"), "ABC+*");
  assertEquals(infixToPostfix.getPostFixString("A-B+C"), "AB-C+");
  assertEquals(infixToPostfix.getPostFixString("A*(B+C*D)+E"),
    "ABCD*+*E+");
  assertEquals(infixToPostfix.getPostFixString("A+B*C+D"), "ABC*+D+");
  assertEquals(infixToPostfix.getPostFixString("(A+B)*(C+D)"), "AB+CD+*");
  assertEquals(infixToPostfix.getPostFixString("A*B+C*D"), "AB*CD*+");
  assertEquals(infixToPostfix.getPostFixString("A+B+C+D"), "AB+C+D+");
  assertEquals(infixToPostfix.getPostFixString("((A*B)+(C/D))"),
    "AB*CD/+");
  assertEquals(infixToPostfix.getPostFixString("((A*(B+C))/D)"),
    "ABC+*D/");
  assertEquals(infixToPostfix.getPostFixString("(A*(B+(C/D)))"),
    "ABCD/+*");
  assertEquals(infixToPostfix.getPostFixString("((A*B)+(C/D))"),
    "AB*CD/+");
  assertEquals(infixToPostfix.getPostFixString("1+2*4/5-7+3/6"),
    "124*5/+7-36/+");
 }
}