Lenguajes y Autómatas ll

La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables. El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda. Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta. Por ejemplo, el

• Pre orden:  (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz: 1. Visite la raíz 2. Atraviese el sub-árbol izquierdo 3. Atraviese el sub-árbol derecho 6,7,9 7,5,1,3,4,6,7 7,3,6,2,5,6,3,1,7,7,3,4,9,5,3,6,8,2,6,8,3,1 Recorrido de arbol infijo El recorrido infijo de un árbol binario es el mismo recorrido inorden, es decir, implica visitar primero el subárbol izquierdo, luego la raíz y por último el subárbol derecho.

  1.1              Pila semántica en un analizador sintáctico   Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o listas enlazadas. Pila: colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope. Las pilas tienen dos operaciones básicas: ·          Push (para introducir un elemento) ·          Pop (para extraer un elemento) Sus características fundamentales es que al extraer se obtiene siempre el último elemento que acabe de insertarse. Por esta razón también se conoce como estructuras de datos LIFO, una posible implementación mediante listas enlazadas seria insertando y extrayendo siempre por el principio de la lista. Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Las pilas y colas son estructuras de dato

3,2,6,5,1,7,1,7,2,5,6,3,3,1,9,3,7 2,7,3,5,1,3,4,2,1,2,6,1,2,8,5,4

 7/5*6+4/3-2*6+3=0.73

8*5/6+7*2/9+4*7= 36.22

  9+5*8-7/4+8*10/6=60.58