Алгоритм преобразования префикса в инфикс с рисунком

Question

---

После некоторого поиска в Google я нахожу его!

Префикс к инфиксу

Этот алгоритм является нехвостым рекурсивным методом. Обращенная входная строка полностью помещается в стек.

prefixToInfix(stack)
   1) IF stack is not empty
     a. Temp -->pop the stack
     b. IF temp is a operator
       i. Write a opening parenthesis to output
       ii. prefixToInfix(stack)
       iii. Write temp to output
       iv. prefixToInfix(stack)
       v. Write a closing parenthesis to output
    c. ELSE IF temp is a space -->prefixToInfix(stack)
    d. ELSE
       i. Write temp to output
       ii. IF stack.top NOT EQUAL to space -->prefixToInfix(stack)

когда вершина стека равна

F (ABC)

и мы вводим алгоритм, «A» записывается в выходной файл, поскольку в данный момент это было значение

temp = A (скажем)

Теперь, как я получаю ' - ' в выходном столбце, поскольку согласно алгоритму следующее временное значение будет "B", которое было извлечено из стека после последнего рекурсивного вызова. Как диаграмма показывает вывод "((A-" ...

Где я делаю неверное предположение? Может ли кто-нибудь попытаться объяснить это?

Answer 1

Я не совсем понимаю ваш вопрос.

Если ваш стек ABC, F(ABC) выдает A, переходит в ветвь d.i. и записывает A для вывода, переходит в d.ii. и выполняет F(BC), который, в конце концов, запишет как B, так и C в вывод.

Если вы хотите, чтобы ваш вывод выглядел так, как на диаграмме, ваш стек должен быть * - A B C (обратите внимание на пробелы между каждым элементом!).

Edit:

(В качестве отступления: все это легче выполнить, чем описано, поэтому я предлагаю вам написать алгоритм в виде программы и запустить его по своему выбору отладчика.)

ОК, поэтому вы сохранили первый * в temp (a), записали a ( (b.i.) и вызвали алгоритм с оставшимся стеком (b.ii.). Это отбрасывает пробел, затем вы сохраняете - в следующей ветке temp, записываете ( и вызываете алгоритм с оставшимся стеком. В какой-то момент вы попадаете в d.ii., вы только что написали A для вывода, давая вам

((A

, а оставшийся стек равен

_B_C

с пробелом сверху и другим пробелом между B и C.
Так что теперь д.ии. находит пространство и больше ничего не делает: эта ветвь управления завершена, и мы возвращаемся туда, откуда пришли, что было d.ii. в вашей - ветке управления. Вы пишете - для вывода в d.iii., Вызываете алгоритм с оставшимся стеком (_B_C) в d.iv., и вот, вы пишете B, ), * и C и последний ).

Просто помните, откуда вы пришли, чтобы вы знали, куда отскочить после завершения текущей рекурсии.