title: Infix to Postfix using Stacks Java
body: <p>I am trying to write a program to convert an infix expression to a postfix expression. </p>
  
  <p>The algorithm that I am using is as follows :</p>
  
  <pre><code>1. Create a stack
  2. For each character t in the expression
     - If t is an operand, append it to the output
     - Else if t is ')',then pop from the stack till '(' is encountered and append 
       it to the output. do not append '(' to the output.
     - If t is an operator or '('
          -- If t has higher precedence than the top of the stack, then push t 
             on to the stack.
          -- If t has lower precedence than top of the stack, then keep popping 
             from the stack and appending to the output until either stack is 
             empty or a lower priority operator is encountered.
  
      After the input is over, keep popping and appending to the output until the
      stack is empty.
  </code></pre>
  
  <p>Here is my code which prints out wrong results.</p>
  
  <pre><code>public class InfixToPostfix
  {
      private static boolean isOperator(char c)
      {
          return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
                  || c == '(' || c == ')';
      }
  
      private static boolean isLowerPrecedence(char op1, char op2)
      {
          switch (op1)
          {
              case '+':
              case '-':
                  return !(op2 == '+' || op2 == '-');
  
              case '*':
              case '/':
                  return op2 == '^' || op2 == '(';
  
              case '^':
                  return op2 == '(';
  
              case '(':
                  return true;
  
              default:
                  return false;
          }
      }
  
      public static String convertToPostfix(String infix)
      {
          Stack&lt;Character&gt; stack = new Stack&lt;Character&gt;();
          StringBuffer postfix = new StringBuffer(infix.length());
          char c;
  
          for (int i = 0; i &lt; infix.length(); i++)
          {
              c = infix.charAt(i);
  
              if (!isOperator(c))
              {
                  postfix.append(c);
              }
  
              else
              {
                  if (c == ')')
                  {
  
                      while (!stack.isEmpty() &amp;&amp; stack.peek() != '(')
                      {
                          postfix.append(stack.pop());
                      }
                      if (!stack.isEmpty())
                      {
                          stack.pop();
                      }
                  }
  
                  else
                  {
                      if (!stack.isEmpty() &amp;&amp; !isLowerPrecedence(c, stack.peek()))
                      {
                          stack.push(c);
                      }
                      else
                      {
                          while (!stack.isEmpty() &amp;&amp; isLowerPrecedence(c, stack.peek()))
                          {
                              Character pop = stack.pop();
                              if (pop != '(')
                              {
                                  postfix.append(pop);
                              }
                          }
                      }
  
                      stack.push(c);
                  }
              }
          }
  
          return postfix.toString();
      }
  
      public static void main(String[] args)
      {
          System.out.println(convertToPostfix("A*B-(C+D)+E"));
      }
  }
  </code></pre>
  
  <p>The program should print <code>AB*CD+-E+</code> but it is printing <code>AB*-CD+E</code>.
  Why is the output incorrect ?</p>
  
  <p>Also, Is there a more elegant solution to this problem. Please share if you have or know one.</p>