Какая из следующих постфиксных нотаций правильно представляет сумму инфиксов 1+2+3+4?

Я тестирую конвертер инфикс-постфикс-инфикс и обнаружил некоторую неопределенность. Например, простая инфиксная сумма

1 + 2 + 3 + 4

можно преобразовать в постфиксный

1 2 + 3 + 4 +

предполагая, что операторы с одинаковым приоритетом не накапливаются. Если они, то я получаю

1 2 3 4 + + +

С другой стороны, все следующие постфиксные выражения можно преобразовать в исходную сумму

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

Все ли эти постфиксные выражения верны?

ОБНОВЛЕНИЕ1

Если бы вы сделали такой преобразователь, в какую форму вы бы выбрали? Мне нужно выбрать один для тестирования.


algorithm notation infix-notation postfix-notation shunting-yard
person Andrei    schedule 09.08.2010    source источник
comment
конечно, есть дополнительная проблема, что с pre/postfix + может быть n-арным, а не двоичным, поэтому 1234+ может быть допустимым выражением   -  person jk.    schedule 09.08.2010

Ответы (3)


arrow_upward
6
arrow_downward

Вам нужно определить дополнительное ограничение.

Математически ваши постфиксные выражения одинаковы. Но на компьютере целочисленное сложение не является коммутативным из-за переполнения.

Замените 1 2 3 4 на a b c d и учтите возможность переполнения. Большинство языков программирования определяют, что a + b + c + d должно оцениваться слева направо, так что a b + c + d + является единственным правильным переводом.

Только когда вы определяете, что порядок оценки «не указан», все версии постфикса эквивалентны. Это имело место для (старых) компиляторов C.

person Henk Holterman    schedule 09.08.2010
comment
+1. Важно то, что они компилируются в то же самое, что и вы. Не то чтобы математически они работали для оператора +, как утверждают другие. - person tster; 09.08.2010
comment
Большинство языков программирования определяют, что a + b + c + d должны оцениваться слева направо. Почему важно то, что делает большинство языков программирования? В ОП не указан язык программирования, а для абстрактных инфиксных выражений я не знаю ни одного такого соглашения слева направо. Я согласен, что ОП должен определить порядок оценки. - person ShreevatsaR; 09.08.2010
comment
@Shreev: Языковая часть предназначена для иллюстрации того, что требуется определение. А лучше перечитайте правила оценки вашего любимца. язык. Это важно. - person Henk Holterman; 09.08.2010
comment
@Henk: Учитывая язык программирования, важно, что делает этот язык программирования. Конечно. Я согласен. Но, не имея никакого языка программирования (как здесь), я не считаю хорошей идеей делать выводы только на основе того, что делает большинство языков программирования. :-) - person ShreevatsaR; 09.08.2010
comment
@Shreev: Суть в том, что + не является (на самом деле) коммутативным. Я думаю, вы слишком много читаете остальным. - person Henk Holterman; 09.08.2010
comment
Я согласен с этим полностью. :-) Спасибо, - person ShreevatsaR; 09.08.2010
comment
Stack Overflow — это сайт вопросов и ответов по программированию - person Dolphin; 10.08.2010
comment
@Dolphin: Да, и что? Это вопрос программирования, о том, как это программировать или что программировать правильно. Какое это имеет отношение к конкурсу популярности, основанному на популярных языках программирования? В вопросе не упоминается конкретный язык программирования, и в зависимости от того, какой язык программирования вы пишете, разные порядки ассоциативности могут быть правильными с точки зрения программирования. Это упоминает программирование достаточно раз для вас? :п - person ShreevatsaR; 10.08.2010
comment
@Henk: Возвращаясь к популярным языкам программирования (хотя это не упоминалось в вопросе), я думаю, что сложение целых чисел является коммутативным в большинстве языков, с которыми я сталкивался, даже с переполнением: независимо от того, идет ли оно по кругу (mod 2 ^ 32) или насыщает (устанавливается на максимальное значение), результаты a+b и b+a одинаковы. Знаете ли вы случай, когда их нет? В любом случае, проблема здесь не в коммутативности, а в ассоциативности, и я согласен с тем, что порядок операций может иметь значение в случаях, когда a, b, c, d — не просто целые числа, а выражения с побочными эффектами. - person ShreevatsaR; 10.08.2010
comment
@Shreev: рассмотрим a + b + c, где c отрицательно. (a+b)+c может переполниться, а a+(b+c) — нет. - person Henk Holterman; 10.08.2010

arrow_upward
5
arrow_downward

Ага, все верно. Они соответствуют следующим инфиксным выражениям в квадратных скобках:

((1 + 2) + 3) + 4
(1 + 2) + (3 + 4)
1 + (2 + (3 + 4))
person David    schedule 09.08.2010
comment
ОК, верно. Я не был ясен в своем вопросе - мне интересно преобразование, а не результат. :) - person Andrei; 09.08.2010
comment
Чтобы быть педантичным, единственный строго правильный порядок - это 1-й. Остальные эквивалентны, но только потому, что сложение ассоциативно. Понятно, что все они дают один и тот же ответ, но ведь и 1441+++ тоже. - person Joel; 09.08.2010
comment
@Joel: Почему 1+2+3+4 означает ((1+2)+3)+4, а не, скажем, 1+(2+(3+4))? Есть ли какое-то соглашение, о котором я не слышал, что инфиксные операции по умолчанию должны оцениваться слева направо/быть левоассоциативными? (Это происходит во многих языках программирования, но ни в коем случае не универсально.) - person ShreevatsaR; 09.08.2010
comment
Фактически, в математике все операции выполняются слева направо, в зависимости от порядка операций. Опять же, для сложения это не имеет значения, но для других операций может. - person Joel; 09.08.2010
comment
@ShreevatsaR: Это важно, например, для векторных перекрестных произведений, которые не являются ни коммутативными, ни ассоциативными. - person Joel; 09.08.2010
comment
@Joel: Я могу заверить вас, что в математике операции с левой ассоциативностью далеко не универсальны. Возьмем приведенный вами пример: для векторных перекрестных произведений a×b×c, скорее всего, будет означать векторное тройное произведение a×(b×c), чем означает (a×b)×c. Функциональная композиция f∘g∘h скорее означает f∘(g∘h), чем (f∘g)∘h. Даже умножение матриц ABC может означать либо (AB)C, либо A(BC) в зависимости от соглашений. Так что, по крайней мере, первое и последнее из трех здесь кажутся одинаково действительными, пока не будет указана ассоциативность (например, путем обращения к популярности в существующих языках программирования. : P) - person ShreevatsaR; 09.08.2010

arrow_upward
2
arrow_downward

+ сбивает с толку - он коммутативен, поэтому на самом деле каждый результат кажется правильным.

Попробуйте заменить + другими операторами: 1 a 2 b 3 c 4.
Правильный результат здесь для левоассоциативных операторов:

1 2 a 3 b 4 c

Итак, в вашем случае я ожидаю 1 2 + 3 + 4 +

person Kobi    schedule 09.08.2010