Question

Which of the following pairs of RPN, reverse Polish notation, formulas are mathematically equivalent?

1. A B - C + and A B C
2. A B + C − and A B C − +
3. A B + C * and A B C + ×

Answer 1

(a) A B - C + and A B C

Reverse Polish notation formulas are evaluated as follows:

A B - C +

Step	Rest of the String	Instruction	Stack
1	A B - C +	BIPUSH A	A
2	B - C +	BIPUSH B	A, B
3	- C +	ISUB	(A - B)
4	C +	BIPUSH C	(A - B), C
5	+	IADD	((A - B) + C)

But for A B C we have

Step	Rest of the String	Instruction	Stack
1	A B C	BIPUSH A	A
2	B C	BIPUSH B	A, B
3	C	BIPUSH C	A, B, C

We can clearly say that they are not mathematically equivalent. But instead of A B C if we have A B C + - then we can say that they are mathematically equivalent as A B C + - is (A - (B + C).

(b) A B + C − and A B C − +

For A B + C − we have

Step	Rest of the String	Instruction	Stack
1	A B + C -	BIPUSH A	A
2	B + C -	BIPUSH B	A, B
3	+ C -	IADD	(A + B)
4	C -	BIPUSH C	(A + B), C
5	-	ISUB	((A + B) - C)

For A B C − + we have

Step	Rest of the String	Instruction	Stack
1	A B C - +	BIPUSH A	A
2	B C - +	BIPUSH B	A, B
3	C - +	BIPUSH C	A, B, C
4	- +	ISUB	(A, (B - C))
5	+	IADD	((A + (B - C))

So, we can say that they are mathematically equivalent.

(c) A B + C * and A B C + ×

For A B + C * we have

Step	Rest of the String	Instruction	Stack
1	A B + C *	BIPUSH A	A
2	B + C *	BIPUSH B	A, B
3	+ C *	IADD	(A + B)
4	C *	BIPUSH C	(A + B), C
5	*	IMUL	((A + B) * C)

((A + B) * C) is equivalent to AC + BC

For A B C + × we have

Step	Rest of the String	Instruction	Stack
1	A B C + x	BIPUSH A	A
2	B C + x	BIPUSH B	A, B
3	C + x	BIPUSH C	A, B, C
4	+ x	IADD	(A, (B + C))
5	x	IMUL	((A * (B + C))

((A * (B + C)) is equivalent to AB + AC

So, they are not mathematically equivalent.

Please comment in case of any doubt.

Hope this helps.