Infix to postfix problem with unary operators

Question

I use the following logic to implement an infix to postfix conversion, to evaluate it later.

• The loop on the infix conversion, and in each iteration, do the following:

  • If space, ignore it.
  • If operator, then keeps popping from the stack and add to the postfix output until the stack is empty or the top of the stack has a lower priority than the current operator. Then, push the current operator.
  • If '(', push it.
  • If '), keep popping and adding to the postfix until you find '('. Then pop the '(' without adding it.
  • Otherwise, then it's a number. Add it directly to the postfix output.

Notes: When I encounter a + or -, I can determine whether it's a binary or unary operator. If it's binary I add it to the stack as '+' or -, but if it's unary I add it as '@' or '$'.

The algorithm works well, except in a case where two unary operators are next to each other.

For example, "--4" becomes "@ 4 @", which is wrong.

What's wrong? What's the correct fix to this issue, that doesn't break other cases?

Answer 1

Looks like you need to change your rules so that you don't pop for successive unary operators. That is, given "--4":

1. You identify the - as a unary operator, and push @
2. You identify the next - as a unary operator, see that the operator on the stack is also a unary operator, and push another @.
3. You see the 4, and output it.
4. At the end of the string, you pop the two unary operators, giving you "4@@".

And of course the unary operators should have higher precedence than any other operator, so that they'll always get popped before any other operator is pushed.