Разговор между постфиксом и инфиксом
Я не могу решить это выражение из постфикса в инфикс. Пожалуйста, помогите мне понять в деталях
5 x y - / x y + 3 ^ 7 / +
Решение
постфикс к инфиксу:
5 x y - / x y + 3 ^ 7 / +
ШАГ
5 х у — /
А) 5xy- / = 5 (х-у) / = (5 / (х-у))
х у +
Б) х у + = (х + у)
(х + у) 3 ^
B.1) (x + y) 3 ^ = ((x + y) ^ 3)
Теперь (5 / (х-у)) ((х + у) ^ 3) 7 / +
= (5 / (x-y)) (((x + y) ^ 3) / 7) +
= (5 / (x-y)) + (((x + y) ^ 3) / 7)
POSTFIX и PREFIX — это выражения, в которых скобки не используются. Приоритет оператора определяется в порядке появления в выражении, поэтому для оценки выражения не нужно искать следующую операцию для выполнения БЫСТРО .
В то время как в выражении INFIX приоритет операторов перезаписывается скобками. следовательно, в инфиксном выражении есть квадратные скобки. Необходимо найти, какую операцию выполнить, например. A + B% D — отсюда МЕДЛЕННЫЙ.
Вот почему конверсия полезна в информатике.
Другие решения
Это не код, а способ, вы должны расширить постфикс до infix:
5 х у — / х у + 3 ^ 7 / +
5 (х-у) / ху + 3 ^ 7 / +
(5 / (х-у)) ху + 3 ^ 7 / +
(5 / (х-у)) (х + у) 3 ^ 7 / +
(5 / (х-у)) ((х + у) ^ 3) 7 / +
(5 / (х-у)) (((х + у) ^ 3) / 7) +
(5 / (х-у)) + (((х + у) ^ 3) / 7)
Это довольно просто:
- Вы читаете аргумент и решаете, является ли он значением или переменной. Если это так, вы помещаете аргумент в стек. Если это не так, это оператор.
- Если у вас есть оператор, вы создаете дерево, состоящее из оператора в качестве корня и столько же аргументов стека, сколько его дочерних элементов. Вы толкаете дерево в стек.
- Когда вы хотите напечатать инфиксную нотацию, вы делаете обход по верху стека (исходная нотация после исправления — это просто пошаговая последовательность того же дерева).
Чтобы справиться с этим в C ++, я создаю базовый класс (Expression) с производным классом, представляющим различные виды узлов (Value, Variable, а также BinaryOperation) и поддерживать std::stack<std::shared_ptr<Expression>>, Кодирование это в основном печатное упражнение.