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

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 в стеке (которые затем заменяются результатом оператора.

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