开发者

Which of the following postfix notations correctly represents infix sum 1+2+3+4?

I am testing an infix-to-postfix-to-infix converter and found some kind of uncertainty. For example, a simple infix sum

1 + 2 + 3 + 4

can be converted to postfix one

1 2 + 3 + 4 +

assuming that operators with equal preced开发者_StackOverflow中文版ence are not accumulated. If they are then I get

1 2 3 4 + + +

On the other hand, all the following postfix expressions can be converted to the initial sum

1 2 + 3 + 4 +
1 2 + 3 4 + +
1 2 3 4 + + +

Are all these postfix expressions correct?

UPDATE1

If you would make such converter, to which form would you choose? I need to choose one for testing.


You need to define an extra constraint.

Mathematically, your postfix expressions are all the same. But on a computer integer addition is not really commutative because of overflow.

Replace 1 2 3 4 with a b c d and consider the possibility of overflow. Most programming languages define that a + b + c + d must be evaluated left-to-right so that a b + c + d + is the only correct translation.

Only when you define that the order of evaluation is 'unspecified' all the postfix versions are equivalent. That was the case for (older) C Compilers.


Yep, all correct. They correspond to the following bracketed infix expressions:

((1 + 2) + 3) + 4
(1 + 2) + (3 + 4)
1 + (2 + (3 + 4))


+ is confusing - it is commutative, so in fact, every result seems correct.

Consider replacing + with other operators: 1 a 2 b 3 c 4.
The correct result here, for left-associative operators, is

1 2 a 3 b 4 c

So, in your case, I'd expect 1 2 + 3 + 4 +

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜