Precedence of operators in infix to postfix conversion

Question

I'm creating a program in C that converts an expression in infix form to postfix form using the reverse polish algorithm through a stack implementation. However, I'm having trouble with how an incoming token having the same precedence as the topmost element of the stack should be placed. For example, given the infix form: (a+b-c/d+e^f^2), the postfix form should be: ab+cd/-ef2^^+. However, my program outputs: ab+cd/-ef^2^+. I think the problem lies with this part of my code:

while(priority(token) <= priority(top_elem(&S)) && !isStackEmpty(&S)){
    x = POP(&S);
    printf("%c", x);
}
PUSH(&S, token);

By the way, this part only executes for operator tokens ('+', '-', '', '/', '^) and the open parenthesis. The priority function returns 0 for the open parenthesis, 1 for '+' and '-', 2 for '' and '/', and 3 for '^'.

I was wondering what I should change in my program. It executes fine for other inputs, though.

Answer 1

You have a problem of associativity: while (a * b) * c == a * (b * c) holds true, the same does not hold for powerTo (or ^): (a ^ b) ^ c != a ^ (b ^ c).

You need to resolve this for each operand when their priorities match up:

while(!isStackEmpty(&S) &&
      (priority(token) < priority(top_elem(&S)) ||
       priority(token) == priority(top_elem(&S)) && !isRightAsoc(token)))
{
    x = POP(&S);
    printf("%c", x);
}
PUSH(&S, token);