elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el ttwitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Notacion Polaca Inversa
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Notacion Polaca Inversa  (Leído 9,343 veces)
gabymar

Desconectado Desconectado

Mensajes: 12



Ver Perfil
Notacion Polaca Inversa
« en: 6 Marzo 2010, 13:37 pm »

Hola, repasando mensajes por el Foro, he encontrado este post https://foro.elhacker.net/ejercicios/sugerencias-t34838.0.html;msg1229723#msg1229723 de Eliptico, y he recordado los viejos tiempos en los que trabajaba con mi calculadora Hewlett Packard, y la utilización que hacía la misma de la Notación Polaca Inversa, el algoritmo propuesto por Eliptico es la conversion de una expresión dada en notacion infixa a notación prefixa o notacion polaca.
   despues de estar un rato pensando en ella, he estado buscando por la red, y he encontrado este pseudocódigo que sirve para la Notación Polaca Inversa o notación postfixa.
  Lo adjunto y propongo la realización del programa en el lenguaje que deseeis, yo concretamente lo voy a realizar en python, que es el que estoy aprendiendo actualmente.

         Algoritmo para N.P.I. http://es.wikipedia.org/wiki/Algoritmo_shunting_yard


En línea

gabymar

Desconectado Desconectado

Mensajes: 12



Ver Perfil
Re: Notacion Polaca Inversa
« Respuesta #1 en: 7 Marzo 2010, 18:55 pm »

Bueno, aqui va el codigo en python para convertir una expresion infixa, o sea normal, en una con notacion polaca inversa.
                                    
Código:
import string

precedencia={'+':1,'-':1,'*':2,'/':2,'^':3}
asociativo={'+':'i','-':'i','*':'i','/':'i','^':'d'}
operador='+-*/^'
papertura='([{'
pcierre=')]}'
sep=',;'
func=['sqrt','log','ln','sin','cos','tg','cotg']
expresion_infixa=''
stack=[]
cola_salida=[]
lista_tipo_token=[]

def cola(token):
#escribe el token en la lista de salida
cola_salida.append(token)

def push(token):
#mete el token en el stack
stack.insert(0,token)
return

def pop():
#saca el primer elemento del stack
return stack.pop(0)

def vacia_stack():
#al final vacia todo el stack en la cola
while len(stack)>0:
cola(pop())

def tipo_char(i):
#comprueba el tipo del caracter encontrado en la lista
#de la expresion de entrada, para agruparlos
if string.digits.find(i)!=-1:
#es una cifra
tipo='num'
elif operador.find(i)!=-1:
#es un operador
tipo='op'
elif papertura.find(i)!=-1 or pcierre.find(i)!=-1:
#es un parentesis
tipo='par'
elif sep.find(i)!=-1:
#es un separador de argumento de funcion
tipo='sep'
else:
#es una letra
tipo='char'
return tipo

def infixa_a_tokens():
lista_tokens=[]
token=''
tipoa=tipo_char(expresion_infixa[0])

for char in expresion_infixa:
tipo=tipo_char(char)
if tipo=='par' or tipo=='sep' or tipo=='op':
#primero guardamos el numero, o var o funcion
# que pudieramos estar acumulando
if tipoa=='char' or tipoa=='num':
lista_tokens.append(token)
lista_tipo_token.append(tipoa)
token=''
     
lista_tokens.append(char)
lista_tipo_token.append(tipo)
tipoa=tipo
else:
#es numero, o variable, o funcion
    #y si antes tambien lo era, concatenamos los caracteres
token=token+char
tipoa=tipo

if tipoa=='num' or tipoa=='char':
lista_tokens.append(token)
lista_tipo_token.append(tipo)
return lista_tokens

# MAIN

expresion_infixa=raw_input("Introduzca funcion : ")
print expresion_infixa

#buscamos los tokens que hay en infixa, y los metemos en una lista
lista=infixa_a_tokens()
print lista

for i in range(len(lista)):
tipo=lista_tipo_token[i]
token=lista[i]

if tipo=='num':
#a la cola salida
cola(token)

elif tipo=='sep':
#separador de parametros de funcion
while stack[0]!='(':
cola(pop())

elif tipo=='par':
#ver si es apertura parent. o cierre
if papertura.find(token)!=-1:
#es apertura
push(token)
else:
#es cierre
comp=papertura[pcierre.find(token)]
while stack[0]<>comp:
cola(pop())
pop()#saca el parentesis y no lo mete en la cola
if len(stack)>0:
if func.count(stack[0])!=0:
#metemos la funcion en la cola
cola(pop())

elif tipo=='char':
#ver si es una funcion
if func.count(token)!=0:
#es una funcion
push(token)
else:
#es una variable, la consideramos como un numero
cola(token)

elif tipo=='op':
if len(stack)>0:
while (len(stack)>0 and
((operador.find(stack[0])!=-1 and
     asociativo.get(token)=='i' and
precedencia.get(token)<=precedencia.get(stack[0])) or
(asociativo.get(token)=='d' and
precedencia.get(token)<precedencia.get(stack[0])))):
cola(pop())
push(token)
vacia_stack()

print cola_salida







« Última modificación: 11 Marzo 2010, 13:52 pm por gabymar » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Notacion polaca « 1 2 »
Java
xAgramonx 14 28,890 Último mensaje 21 Octubre 2012, 09:09 am
por Rocio Sol
notación polaca inversa
Programación C/C++
david_BS 0 3,530 Último mensaje 31 Marzo 2012, 19:26 pm
por david_BS
[Duda] token/strtok /Notacion Polaca Inversa
Programación C/C++
digitalx2 1 1,403 Último mensaje 23 Septiembre 2013, 19:10 pm
por eferion
Problema con la notación de punteros
Programación C/C++
apoeti 5 1,667 Último mensaje 11 Julio 2014, 00:32 am
por apoeti
notacion JSON error
PHP
geshiro 1 1,468 Último mensaje 18 Mayo 2016, 10:10 am
por moikano→@
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines