Infix to Postfix using Stacks Java

Question

I am trying to write a program to convert an infix expression to a postfix expression.

The algorithm that I am using is as follows :

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.

Here is my code which prints out wrong results.

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<Character> stack = new Stack<Character>();
        StringBuffer postfix = new StringBuffer(infix.length());
        char c;

        for (int i = 0; i < infix.length(); i++)
        {
            c = infix.charAt(i);

            if (!isOperator(c))
            {
                postfix.append(c);
            }

            else
            {
                if (c == ')')
                {

                    while (!stack.isEmpty() && stack.peek() != '(')
                    {
                        postfix.append(stack.pop());
                    }
                    if (!stack.isEmpty())
                    {
                        stack.pop();
                    }
                }

                else
                {
                    if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                    {
                        stack.push(c);
                    }
                    else
                    {
                        while (!stack.isEmpty() && 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"));
    }
}

The program should print AB*CD+-E+ but it is printing AB*-CD+E. Why is the output incorrect ?

Also, Is there a more elegant solution to this problem. Please share if you have or know one.

Answer 1

Issue is with your else part:

               if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                {
                    stack.push(c);
                }
                else
                {
                    while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
                    {
                        Character pop = stack.pop();
                        if (pop != '(')
                        {
                            postfix.append(pop);
                        }
                    }
                }

                stack.push(c);

So here you are pushing the same c element twice with stack.push() when you see stack is not empty and precedence match is higher.

So put this stack.push within else part or remove the push from if condition.

Another issue is, when at the end you have some operators within the stack you dont pop them out.

Here's the code that i came up with for your case:

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<Character> stack = new Stack<Character>();
    StringBuffer postfix = new StringBuffer(infix.length());
    char c;

    for (int i = 0; i < infix.length(); i++)
    {
        c = infix.charAt(i);

        if (!isOperator(c))
        {
            postfix.append(c);
        }

        else
        {
            if (c == ')')
            {

                while (!stack.isEmpty() && stack.peek() != '(')
                {
                    postfix.append(stack.pop());
                }
                if (!stack.isEmpty())
                {
                    stack.pop();
                }
            }

            else
            {
                if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
                {
                    stack.push(c);
                }
                else
                {
                    while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
                    {
                        Character pop = stack.pop();
                        if (c != '(')
                        {
                            postfix.append(pop);
                        } else {
                          c = pop;
                        }
                    }
                    stack.push(c);
                }

            }
        }
    }
    while (!stack.isEmpty()) {
      postfix.append(stack.pop());
    }
    return postfix.toString();
}

public static void main(String[] args)
{
    System.out.println(convertToPostfix("A*B-(C+D)+E"));
}

Answer 2

I think above answer is not correct.

This is the version corrected by me :

package Stack;

import java.util.Stack;

/*
 * 
Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.

 */
public class InfixToPostFixEvalution {

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

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

        case '*':
        case '/':
            return 2;

        case '^':
            return 3;
        }
        return -1;
    }

    // A utility function to check if the given character is operand
    private static boolean isOperand(char ch) {
        return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
    }

    public static String convertToPostfix(String infix) {
        Stack<Character> stack = new Stack<Character>();
        StringBuffer postfix = new StringBuffer(infix.length());
        char c;

        for (int i = 0; i < infix.length(); i++) {
            c = infix.charAt(i);

            if (isOperand(c)) {
                postfix.append(c);
            } else if (c == '(') {
                stack.push(c);
            }
            // If the scanned character is an ‘)’, pop and output from the stack
            // until an ‘(‘ is encountered.
            else if (c == ')') {

                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                }
                if (!stack.isEmpty() && stack.peek() != '(')
                    return null;
                else if(!stack.isEmpty())
                    stack.pop();
            }
            else if (isOperator(c)) // operator encountered
            {
                if (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) {
                    postfix.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            postfix.append(stack.pop());
        }
        return postfix.toString();
    }

    public static void main(String[] args) {
        System.out.println(convertToPostfix("a+b*(c^d-e)^(f+g*h)-i"));
    }
}