Infix to postfix algorithm that takes care of unary operators

Question

The I/p to the algo will be an expression like this:

a+(-b)
a*-b+c

i.e any expression that a standard C compiler would support.

Now I've the input already formatted as a stream of tokens , the tokens contain info whether its an operator or an operand. The algorithm should take this in and give me a postfix expression that I can evaluate.

If I use the standard conversion algo, I cant differentiate between an unary and a binary op. Like a*(-b) would give me ab-* ,which would evaluate in the wrong way.

Answer 1

If an operator is the first thing in your expression, or comes after another operator, or comes after a left parenthesis, then it's an unary operator.

You have to use other symbols for unary operators in your output string, because otherwise it is not possible to distinguish between binary and unary variants in the postfix notation.

Answer 2

In your input, when you have 2 consecutive operators, the second operator will be unary. If you have more consecutive operators, all but the first will be unary operators.

Transform all your unary - operators to an operand -1 and an operator *, and remove all unary + operators.

If the first element is an operator, it is an unary operator.

Parenthesis are a special case, but you can do a first pass in which you ignore them. In the following example - is consecutive to *.

4*(-(5))

and your tokens would become:

4
*
(
-1
*
(
5
)
)

Answer 3

You could simply convert -6 to 06- to eliminate unary operators completely. I like this approach since it is more orthogonal and you do not need to take care of special cases when processing.

An alternative approach is to use different symbols for the unary and the binary versions of operators using the same symbol, eg. - remains binary minus and ~ becomes negation sign.