Разное

Есть известный алгоритм преобразования из инфиксной нотации в ОПН: кликни меня
По-моему, приведённый алгоритм подходит для унарных и бинарных операторов, а как он будет выглядеть для тернарного? Скажем, того же a ? b : c

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

А выглядеть алгоритм будет как-то, но по-разному :) для C и php .

Либо я что-то недопонял, либо Вы мне говорите про вычисление ОПН с тернарным оператором. А мне нужен именно перевод из инфиксной нотации.

из инфиксной в какую?
фиксной нотации нет тернарных операций.
В постфиксной нотации нет условных операций.

> из инфиксной в какую?
Постфиксную.

> фиксной нотации нет тернарных операций.
Я не понял предложения.

> В постфиксной нотации нет условных операций.
То есть? Например, у нас есть стек операндов, я встечаю оператор "?:" (обозначу его так), я должен просто вытолкнуть три операнда из стека, протолкнуть обратно уже 1 значение. Кстати, тоже самое и Вы написали.

Как вообще Вы бы сами делали разбор выражения а-ля "2 + 2*2 ? 6 - 3 : (2 - 6) / 2"?

>> из инфиксной в какую?
>Постфиксную.
>
>> фиксной нотации нет тернарных операций.
>Я не понял предложения.
Пардон. В инфиксной нотации нет тернарных операций.
Они (она - точнее) есть в синтаксисе-семантике языка С и некоторых других.



>> В постфиксной нотации нет условных операций.
>То есть? Например, у нас есть стек операндов, я встечаю оператор "?:" (обозначу его так), я должен просто вытолкнуть три операнда из стека, протолкнуть обратно уже 1 значение. Кстати, тоже самое и Вы написали.
>
>Как вообще Вы бы сами делали разбор выражения а-ля "2 + 2*2 ? 6 - 3 : (2 - 6) / 2"?

Я бы делал как С.
Php делает по-другому.
Ассоциативность разная.

> В инфиксной нотации нет тернарных операций.

Это как? Не подходит под определение или че?

> Я бы делал как С.

Меня интересует не ожидаемый результат, а сам алгоритм разбора. Выражения с бинарными и унарным операциями без каких-либо проблем обрабатываются с помощью двух алгоритмов: перевода из инфиксной записи в постфиксную и алгоритма вычисления значения выражения в постфиксной нотации. Всё. А как обрабатывать a ? b : c я не знаю. Тут уже подумать надо.

Кстати, какие преимущества у префиксной записи перед постфиксной (и наборот)?

Условную операцию в чистом виде (т.е. такую, которая не делала бы попыток вычислить поддерево ложного условия) в постфиксной нотации не записать ( а в префиксной - легко, ближайший пример - IF() в MySQL.)
А чтобы выполнять вычисления - так или иначе придется дерево переводить в постфиксную нотацию или её подобие, поскольку невозможно выполнить конечную операцию, не имея уже вычисленных аргументов, и неважно, реализован стек нотации на стеке процесса целиком, или его верхушку генератор кода отобразил на свободные регистры.
Это к вопросу о преимуществах и недостатках.

А что касается того, как именно - то тут всё просто. Если на предвычисленные поддеревья наплевать (хотя в них по-моему самый сок условной операциии), то можно ж представить её из двух инфиксных:

С ? Et : Ef === C ? (Et : Ef)
либо
С ? Et : Ef === (C ? Et ) : Ef
и дальше уже выполнять перевод согласно общепринятым алгоритмам.
(см. рисунок)

и в зависимости от выбранной схемы ассоциативности уже будет раскрываться неоднозначность семантики С и PHP
c1?et1:c2?et2:ef2 === c1?et1:(c2?et2:ef2) //C
c1?et1:c2?et2:ef2 === (c1?et1:c2)?et2:ef2 // PHP

> Условную операцию в чистом виде (т.е. такую, которая не делала бы попыток вычислить поддерево ложного условия) в постфиксной нотации не записать ( а в префиксной - легко, ближайший пример - IF() в MySQL.)

Блин, точно, говно выходит.

> А что касается того, как именно - то тут всё просто. Если на предвычисленные поддеревья наплевать (хотя в них по-моему самый сок условной операциии), то можно ж представить её из двух инфиксных:

> С ? Et : Ef === C ? (Et : Ef)
> либо
> С ? Et : Ef === (C ? Et ) : Ef
> и дальше уже выполнять перевод согласно общепринятым алгоритмам.
> (см. рисунок)

Это вышло, спасибо.