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.

Agincourt

Where's the question? – Thermometer

It use another symbol(e.g '_') in the output for the symbol as a unary operator '-' – Pinole

The question is : Suggest a modification of the standard algo or a new algo that sorts my problem. – Agincourt

@user2512249 Just use different symbol for unary -, as @Pinole suggested – Thermometer

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.

Accustomed

What if there are several consecutive operators? Does that rule still apply? E.g. 5+-2 is okay, but what about 5+-+-2? – Faradmeter

@htossli yes it very much does – Accustomed

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
)
)

Greenquist

I saw in the end you preferred the other answer, indeed you needed a special symbol in your output for unary operators. In the end how did it look your converted string for a*(-b)? Did you stick to C notation or you were accepting also things like 4(5-2), in which the * symbol is only implied? – Greenquist

well I had defined a class with the following members: int opcode , string operand. I converted the input string first to an array of this class , so while scanning I checked if its a unary or a binary op, and accordingly assigned my opcode. Then I converted this to postfix and while evaluating just had if-else conditiosn where I took care of unary operators (I already know which are unary since I've assigned them a particular set of opcodes) – Agincourt

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.

Trypanosome

But we have to use different way for different operators. How can we deal with ln(x) ? – Jorum