Prefijo para Infijo Conversión Algoritmo con la figura
-
09-10-2019 - |
Pregunta
Después de algún búsqueda de google lo encuentro!
Prefijo para Infijo
Este algoritmo es un método recursivo no cola. La cadena de entrada invertida está completamente empujado en una pila.
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)
cuando la parte superior de pila es
F (ABC)
y entramos en el algoritmo, "A" se escribe en la salida, ya que era actualmente el valor de
temp = A (digamos)
Ahora, ¿cómo recibo el mensaje ' - en la columna de salida como de acuerdo con el algoritmo siguiente valor de temperatura será "B", que se hizo estallar de la pila después de la última llamada recursiva. Como el diagrama representa salida "((A-" ...
¿Dónde estoy haciendo la suposición incorrecta? Es posible que alguien tome la molestia de explicarlo?
Solución
Yo no entiendo muy bien su pregunta.
Si su pila es ABC
, F(ABC)
aparece la A, entra en la rama d.i. y escribe una A en la salida, continúa en d.ii. y realiza F(BC)
, que, al final, de escritura tanto la B y C a la salida.
Si desea que su salida se vea como lo hace en el diagrama, usted necesitará su pila para ser * - A B C
(tenga en cuenta los espacios entre cada elemento!).
Editar:
(Dicho sea de paso:. Todo esto es más fácil paso a través de los descritos, por lo que sugiero que escriba el algoritmo como un programa y lo inicia en su elección de depurador)
Aceptar, por lo que ha almacenado en el primer *
temp
(a), escrito un (
(B.I.), y se llama el algoritmo con la pila restante (B.II.). Esta tira a la basura un espacio en blanco, a continuación, se almacena una -
en temp
de la siguiente rama, escribe un (
, y llamó el algoritmo con la pila restante. En algún momento, se termina en d.ii., que acaba de escribir una A en la salida, lo que le
((A
y la pila restante es
_B_C
con un espacio en la parte superior y otro espacio entre B y C.
Así que ahora d.ii. se encuentra el espacio y no hacer nada más: esta rama de control está hecho, y volvemos a donde venimos, que era d.ii. en su rama de control -
. Se escribe el -
a la producción en D.III., Llame al algoritmo de la pila restante (_B_C
) en d.iv., y ahí lo tienes, escribiendo el B
, un )
, la *
y C
y el último )
.
Sólo recuerde de dónde viene, para que sepa dónde saltar de nuevo después de su recursividad actual está hecho.