Pasar de infijo a postfijo
Edwin Duran
un compañero de la uni tine una tarea y el profesor la quiere en
visualfoxpro, he visto mucho ejemplo en C++ y java y no entiendo nada he
buscado en san google algun algoritmo pero nada, si tienen lago favor de
pasarlo
gracias
Pedro
"Edwin Duran" <edwin_...@hotmail.com> escribió en el mensaje
news:uOsRFdMA...@TK2MSFTNGP04.phx.gbl...
WEHS
Aqui hay una explicación y un algoritmo que te puede servir mucho más que un
ejemplo de codigo.
Expresiones Algebraicas: Prefija, Infija, y Postfija
Si el lector tiene conocimientos acerca de Expresiones Algebraicas en forma
prefija, infija, y postfija, entonces puede saltarse esta sección y
continuar con la sección 4. Algoritmo: Pasar de Infija a Postfija.
Las expresiones algebraicas que usamos en el mundo occidental son las
llamadas infijas. Esto quiere decir que los operadores están colocados entre
medias de dos operandos. Por ejemplo, "2+3". "2" y "3" son operandos y "+"
es el operador, el cual está situado entre los operandos.
Las expresiones de forma prefija y postfija siguen la misma lógica que la
infija, excepto que la prefija sitúa el operador antes (pre-) de los dos
operandos y postfija, detrás (post). En el ejemplo anterior, "2+3", la
expresión en forma prefija sería "+23", y en forma postfija, sería "23+".
Otro ejemplo más complejo:
Infija: 2*3+9/3 = 6+9/3 = 6+3 = 9
Prefija: +*23/93 = +6/93 = +63 = 9
Postfija: 23*93/+ = 693/+ = 63+ = 9
La forma de convertir de infija a prefija o postfija es relativamente
simple:
1. Se dejan los números en la misma colocación: 2 * 3 + 9 / 3
2. Se "borran" los operadores: 2 3 9 3
3. Ahora se colocan los operadores a la derecha (prefija) o izquierda
(postfija) de los operandos. Para prefija: + * 2 3 / 9 3, y para postfija: 2
3 * 9 3 / +
Las ventajas de tener una expresión algebraica en prefija o postfija en vez
de infija son:
* Evaluando una expresión en forma prefija se asemeja a programar en
ensamblaje: <instrucción> <operando1> <operando2>
* Evaluando una expresión en forma postfija es más fácil a la hora de
implementar analizadores de lenguajes, calculadoras (como veremos pronto),
etc..
* Las formas prefijas o postfijas no contienen paréntesis, como los
suele tener la forma infija. Ejemplo:
Infija: 2*(3+9)/3 = 2*12/3 = 24/3 = 8
Prefija: /*2+393 = / * 2 12 3 = / 24 3 = 8
Postfija: 239+*3/ = 2 12 * 3 / = 24 3 / = 8
La ventaja de la forma infija es que es más sencilla de dictar, ya que es
más lógica (al menos para nosotros humanos) que las formas prefijas y
postfijas. Estas dos últimas formas necesitan tener la expresión entera
antes de poder evaluar, mientras que la infija suele ser evaluada a medida
que se vaya obteniendo información. Hay quizá otra ventaja al usar la forma
infija, los operadores separan una agrupación de dígitos de otra; así es más
fácil de leer los números, que las formas prefijas y postfijas.
saludos,
--
William Hernández
VFP9 SP2/Vista Bussines
Santiago, Chile.
"Pedro" <pedri...@hotmail.es> escribió en el mensaje de noticias
news:uc3xWkMA...@TK2MSFTNGP05.phx.gbl...
Edwin Duran
estos son algunos link
http://nereida.deioc.ull.es/~pl/perlexamples/node150.html
http://www.programacion.com/foros/29/msg/107944/
"Pedro" <pedri...@hotmail.es> escribió en el mensaje
news:uc3xWkMA...@TK2MSFTNGP05.phx.gbl...
Edwin Duran
De un algoritmo que encontre he echo esto pero me falta algo y no he podido
decifrar, espero que me ayuden ya que esto es para entregar el dia 19\08\08
a la cinco de la tarde le dejo el codigo con el texto del algoritmo
Clea
Store "" To E, P
c1= 0
Set Step On
*INICIO
*Crear pila y la lista de salida, inicialmente vacias.
Dimension pila(100)
texto = "(6+8*5)" &&/(9-12/2)"
* MIENTRAS lista de entrada no este vacia y no se ha encontrado ningun error
HACER
For i = 1 To Len(texto)
E = Alltrim(Substr(Alltrim(texto), i, 1))
If Empty(E)
Loop
Endif
*Extraer el primer termino de la lista (lo llamaremos E)
*SEGUN-SEA E
Do Case
*CASO E es número :
Case Inlist(E,"0","1","2","3","4","5","6","7","8","9")
P = P+ E
* Insertar E al final de la lista de salida
*CASO E es la variable x :
Case Between(Asc(E),65,72)
P = P+ E
* Insertar E al final de la lista de salida
*CASO E es un paréntesis izquierdo :
Case E="("
*Insertar E en la pila
c1 = c1 + 1
pila(c1)= E
*CASO E es un paréntesis derecho :
Case E=")"
*MIENTRAS La pila no este vacía y su cima no sea un paréntesis izquierdo
HACER
*Extraer elemento de la pila
*Insertarlo al final de la lista de salida
c=1
Do While !Empty(pila(c)) And pila(c) <> "("
P = P +pila(c)
c = c + 1
*FIN-MIENTRAS
Enddo
*SI Encontramos el parentesis izquierdo ENTONCES
If pila(c) = "("
*Extraerlo de la pila y destruirlo
pila(c)=""
*SINO
Else
*Se ha detectado un ERROR 2
Messagebox("Error en parentesis")
*FIN-SI
Endif
E =""
*Destruir E
*CASO E es un operador :
Case Inlist(E,"+","-","*","/","%","^")
Do Case
Case E ="-"
valor = 1
Case E ="+"
valor = 2
Case E ="/"
valor = 3
Case E ="*"
valor = 4
Case E ="^"
valor = 5
Enddo
c=1
Do While !Empty(pila(c))
*MIENTRAS La pila no este vacía y su cima sea un operador de precedencia
mayor o igual que la de E HACER
*Extraer elemento de la pila
If pila(c) <> "("
P = P +pila(c)
Endif
c = c + 1
*Insertarlo al final de la lista de salida
*FIN-MIENTRAS
Enddo
* Insertar E en la pila
c1=c1 +1
pila(c1)= E
*FIN-SEGUN-SEA
Endcase
*FIN-MIENTRAS
Next i
* MIENTRAS Pila no esté vacía HACER
c =1
*SET STEP ON
Do While !Empty(pila(c))
P = P+pila(c)
?P
c = c + 1
* Extraer elemento de la pila
* Insertarlo al final de la lista de salida
* FIN-MIENTRAS
Enddo
* Destruir pila
* FIN