Associativity rule in Infix to Postfix expression

Question

My infix to postfix algorithm using stack:

static int Prec(char ch) {
    switch (ch) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '^':
        return 3;
    }
    return -1;
}

static String infixToPostfix(String exp) {
    String result = new String("");
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < exp.length(); ++i) {
        char c = exp.charAt(i);
        if (Character.isLetterOrDigit(c))
            result += c;
        else if (c == '(')
            stack.push(c);
        else if (c == ')') {
            while (!stack.isEmpty() && stack.peek() != '(')
                result += stack.pop();
            stack.pop();
        } else {
            while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())) {
                result += stack.pop();
            }
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        if (stack.peek() == '(')
            return "Invalid Expression";
        result += stack.pop();
    }
    return result;
}

Input: K+L-M*N+(O^P)*W/U/V*T+Q^J^A

Expected Output: KL+MN*-OP^W*U/V/T*+QJA^^+

Actual Output: KL+MN*-OP^W*U/V/T*+QJ^A^+

• If current operator and operator at top of stack have the same precedence then check their associativity,
• If associativity of operators is right to Left, then simply push operator onto the stack.
• If associativity of operators is left to right, then pop operator from stack and check for associativity again for current operator and operator at top of stack.

The difference in the expected and actual output is when the sub-expression ^J^A is evaluated. When character Q is reached, the stack contains ['+']. I output the operand Q and move to the next character in the expression. With respect to the above rule, the following should happen:

• ^ is the next character after Q. Since ^ has a higher precedence than +, I pushed it into the stack, ['+','^'] and moved pointer to J.
• Output J as it's an operand and move pointer.
• Pointer is now at ^. Since top of stack also contains a ^, they have the same precedence so we need to check associativity rule which is right to left. Thus, we push ^ into the stack. So the stack looks something like ['+','^','^'].
• Pointer is now at last character A so just output it.
• Since we have reached end of expression, we can start popping out the operators from the stack so the postfix form of subexpression will look like QJA^^+.

However, my code doesn't work for associativity. Can someone explain how associativity can be handled in the above implementation?

Answer 1

It is an easy fix. You need to update the while loop condition from:

while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))

To:

while (!stack.isEmpty() && (prec(c) < prec(stack.peek()) || (prec(c) == prec(stack.peek()) && isLeftToRightAssociative(stack.peek()))))

Here is the method isLeftToRightAssociative():

public static boolean isLeftToRightAssociative(Character operator)
{
    //You can also use return operator != '^' as an alternative to the if-else given below
    if (operator == '^') return false;
    else return true;      
}

I should add that your code will not produce correct output if the user inputs an expression which contains unary operators. If you will be working with unary operators, you should update your code.