Prefix to Infix Conversion Algorithm with figure

Question

---

After some google search I find it!

Prefix to Infix

This algorithm is a non-tail recursive method. The reversed input string is completely pushed into a stack.

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)

when the Stack top is

F(ABC)

and we enter the algorithm, "A" is written to the output as it was currently the value of

temp=A (say)

Now how I get '-' on the output column as according to the algorithm the next temp value will be "B" which was popped from the stack after the last recursive call. How the diagram is showing output "((A-" ...

Where I am doing the incorrect assumption ? Could someone take the trouble in explaining it ?

Answer 1

I don't quite understand your question.

If your stack is ABC, F(ABC) pops the A, goes into branch d.i. and writes an A to output, goes on into d.ii. and performs F(BC), which will, in the end, write both the B and C to output.

If you want your output to look like it does on the diagram, you'll need your stack to be * - A B C (note the spaces between every element!).

Edit:

(As an aside: all this is easier stepped through than described, so I suggest you write the algorithm as a program and start it in your choice of debugger.)

OK, so you have stored the first * in temp (a), written a ( (b.i.), and called the algorithm with the remaining stack (b.ii.). This throws away a blank, then you store a - in the next branch's temp, write a (, and called the algorithm with the remaining stack. At some point, you end up in d.ii., you have just written an A to output, giving you

((A

and the remaining stack is

_B_C

with a space on top and another space between B and C.
So now d.ii. finds the space and doesn't do anything anymore: this control branch is done, and we go back to where we came from, which was d.ii. in your - control branch. You write the - to output at d.iii., call the algorithm with the remaining stack (_B_C) at d.iv., and there you go, writing the B, a ), the * and C and the last ).

Just remember where you came from, so you know where to jump back after your current recursion is done.