Постфикс для инфикса с унарными / бинарными операторами

Question

Я пытаюсь сделать конвертер из постфикса в инфиксную запись и мне нужна помощь. Уже существует вопрос о преобразовании из инфикса в постфикс , который приводит пример, который мне не удается преобразовать обратно. (Примечание: там отсутствует знак минус!)

Ниже приведен вывод моего конвертера, где 1-й столбец - это постфиксный ввод, 2-й - мой инфиксный вывод, а 3-й - то, что я, вероятно, должен получить (?):

2 -                      =   - 2                           =?    - 2                       true
1 + 2 +                  =   + 1 + 2                       =?    + 1 + 2                   true
1 + 2 + +                =   + (+ 1 + 2)                   =?    + 1 + + 2                 false
1 + 2 + + 3 - - 4 - -    =   - (- (+ (+ 1 + 2) - 3) - 4)   =?    + 1 + + 2 - - 3 - - 4     false

Как вы думаете, возможно ли решить эту проблему, или две последние строки на самом деле правильно преобразованы? Как бы вы написали алгоритм для решения этой проблемы?

Пожалуйста, предположим, что больше операторов (не только + и -) могут быть установлены как унарные, так и двоичные, где унарные операторы имеют более высокий приоритет, чем двоичные.

Ссылки

1. Ruby Quiz # 148: Постфикс для Infix , также через Группы Google
2. Алгоритм шунтирования (C, Python, Perl) с поддержкой унарного оператора в LiteratePrograms

Answer 1

Постфиксная нотация не имеет концепции приоритета, поскольку операнды для любого оператора всегда являются верхними значениями N в стеке (которые затем заменяются результатом оператора.

Одна проблема с постфиксомпримечание состоит в том, что он плохо справляется с символами операторов, которые могут ссылаться на различные операторы в зависимости от количества операндов (например, -, который может обозначать как унарный, так и двоичный минус). Единственный выход из этого заключается в том, чтобы каждый оператор имелуникальный символ, представляющий его.