Answer to Question #260328 in Electrical Engineering for jjj

Question

1. Convert the following arithmetic expressions from infix to reverse Polish notation.

a. A * B + C * D + E * F

b . A * B + A * (B * D + C * E)

c. A + B * [C * D + E * (F + G)]

d. A * [B + C * (D + E)] / f * (G + H)

Answer 1

The first opening parenthesis ( after the opening bracket) is unpaired we can ignore it here.

A B C D * E F G + * + *+ , will work. So will, G F + E * D C * + B * A +. You can also swap the arguments for any commutative operator.

Starting at the deepest parentheses

(F+G) = F G +

This gets multiplied by E

F G + E *

Then added to C D *

F G + E * C D * +

Then the whole kaboodle gets multiplied by B

F G + E * C D * + B *

and added to A

F G + E * C D * + B * A +

The maximum stack depth of 3 appears when we enter D in this last sequence.

We can emulate an infix parser by hand to (painstakingly) show the steps are correct.

If we are entering ad hoc., as in the first example of the top paragraph, A sits on the bottom of the stack until the end...

A

the operation + has to wait…

A

_+

then B has to wait…

A B

_+

and the operation * waits

A B

_ * +

we find the bracket and redundant parenthesis which we are ignoring…

A B

_ [ * +

and C…

A B C

_ [ * +

with the operation *…

A B C

_ * [ * +

along comes D…

A B C D

_ * [ * +

then +…

A B C D

_ + * [ * +

* has precidence over + and both arguments are on top of the data stack , so we can condense them and pull the * operation…

A B CD*

_ + [ * +

E appears…

A B CD* E

_ + [ * +

then *…

A B CD* E

_ * + [ * +

a new opening parenthesis…

A B CD* E

_ ( * + [ * +

“F + G”…

A B CD* E F G

_ + ( * + [ * +

Then the closing parenthesis, so everything back to the open, just the plus, will be condensed…

A B CD* E FG+

_ * + [ * +

Now the closing bracket triggers the condensation of the two enclosed operations…

A B CD*EFG+*+

_ * +

and <end-of-line> condenses the rest…

ABCD*EFG+*+* +