Árboles Binarios para Expresiones Aritméticas

Clase 31 de 40 • Curso de Matemáticas Discretas

Resumen

Los árboles también nos sirven para representar expresiones aritméticas, para ello debe cumplir con las siguientes condiciones:

• Los vértices terminales son operandos. • Los vértices internos son operadores. • La raíz siempre debe ser un operador.

Así como vimos las diferentes formas para recorrer un árbol, las expresiones aritméticas tienen también sus propias formas:

• Pre fijo: raíz-izquierda-derecha • In fijo: izquierda-raíz-derecha • Pos fijo: izquierda-derecha-raíz

Ruben Eduardo Acosta Vela

student•

De que nos sirve escribir una operacion arimetica en notacion de arbol?
Pregunto porque solo veo que los elementos quedan en un total desorden y sin posibilidad de operar; digamos en la notacion prefija, al inicio, no puedo operar “/+”

Sergio Orduz

teacher•

@Byhako gracias por hacer parte de este curso, Las notaciones fijas, infijas y posfijas son formas en las que los lenguajes de programación pueden entender nuestras expresiones. Dependiendo del lenguaje de programación que manejes entenderá una o la otra 😄

Hector Vasquez

student•

php y js y la mayoría de los lenguajes conocidos, tienen notación “Infija”: a+b

Haskell, que es lenguaje funcional, tiene notación “Prefija”: +ab

Esto último, porque haskell tiene todo como funciones, incluso los operadores. Si le cambiamos los nombres a los operadores y los convertimos en funciones, se puede entender mejor:

*c+ab = c*(a+b)

Funcional:
*c+ab = multiplicar( c, sumar(a,b) )

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

Reglas de las expresiones aritméticas

Los vértices terminales son operandos (números), con los que haremos operaciones.
Los vértices internos o raíces van a ser los operadores.
El nodo raíz siempre debe ser un operador y va a ser el operador con mas relevancia dentro de nuestra expresión aritmetica
El orden de resolución de las operaciones aritmética siempre es: paréntesis, raíces, potencias, multiplicación, división, suma y resta

Maneras de recorrer una expresión aritmética
Al igual que los arboles tenemos tres maneras de recorrer una expresión aritmética:

Pre fijo: raíz, izq, der
In fijo: izq, raíz, der
Pos fijo: izq, der, raíz

Andres Jeriha

student•

Esto ayuda a aclarar porqué en distintos lenguajes de programación las expresiones aritméticas se escriben distinto.

Mientras que en python y javascript lo hacemos escribiendo:

3 + 4

y nos sale 7

en Racket lo hacemos escribiendo:

+ 3 4

y obtenemos el mismo resultado

Alfredo Napoleón Noboa Cárdenas

student•

Lo único que te faltó Sergio fue poner algún ejemplo de usos de las notaciones, beneficios de cada una de ellas, por ejemplo HP en sus calculadoras te deja escoger entre el modo algebraico (infijo) y el modo RPN (posfijo), la ventaja del RPN era que evitaba la ambigüedad al escribir las expresiones algebraicas y era más eficiente también, ya que evitaba que escribas paréntesis y tecleabas también menos ya que al ingresar al final el operador ya no tenías que pulsar la tecla enter o la tecla igual para ejecutar el cálculo simplemente con el ingreso del operador ya te daba el resultado.

Alex Camacho

teacher•

Que buen complemento a la clase, gracias por el aporte :)

Carlos Fernando Aguilar González

student•

Les comparto un recurso mnemotécnico que vi en otro curso de Platzi para aplicar la jerarquía de operadores: PEMDAS (Paréntesis, Exponentes, Multiplicaciones, Divisiones, Adiciones o sumas, y Sustracciones o restas).

Miguel Andres Rendon Reyes

student•

jajaja me acuerdo

Henry Mendiburu Díaz

student•

Erik Ucenik

student•

Es curioso que no todos usan la notación entrefija. Por ejemplo lisp utiliza la notación prefija en su lugar:

(+ 2 2)
>> 4

Luis Mojica

teacher•

Amé esta clase :green_heart:

Miguel Angel Malarin Flores

student•

LO QUE PUEDO OBSERVAR ES QUE LA EXPRESION " IN FIJA " ES LA MAS PARECIDA AL ENUNCIADO ORIGINAL , CLARO MATEMATICAMENTE HABLANDO

Raul Armas

student•

Interesante x3

Wilson Fernando Antury Torres

student•

**Expresiones aritméticas con árboles: **

Los vértices hijos serán los operandos.
Los vértices internos serán los operadores.
La raíz siempre debe ser un operador.
Debe aplicarse las propiedades de precedencia de operadores: ()[], raíces y potencias, */, +-
pre-fijo: se inicia desde el vértice padre, sigue el hijo izquierdo y por último el hijo derecho.
in-fijo: inicia leyendo el hijo izquierdo, después el padre y por último el hijo derecho
pos-fijo: la lectura se inicia con el hijo izquierdo, después el hijo derecho y por último el padre.

Elisa Zamarron Muñoz

student•

Sinceramente para mi es más facil construir el árbol desde el operador con mayor prioridad, es decir iniciar con la raíz, cuestión de gustos.

Arturo Barrios

student•

Transformación de la expresión aritmética a Notación Pos - Fija

Miguel Andres Rendon Reyes

student•

Esto està igualito a un Xpath, ¿No creen?

Henry Mendiburu Díaz

student•

XPath (XML Path Language) es un lenguaje que permite construir expresiones que recorren y procesan un documento XML.

Nicolas Humberto Sulca Vega

student•

En este capitulo habla de arboles, pero todos los capitulos anteriores a este no se menciona en ningun momento el tema ni los tipos de arboles, me parece que este capitulo va despues del capitulo “recorrido de arboles” que esta varias clases adelante.

Sergio Orduz

teacher•

gracias Nicolas por estar pendiente… parece que ya fue corregido

Ricardo Soler

student•

Este tema me ha recordado el lenguaje de programacion LISP (no se hoy en dia si se sigue usando pero yo lo usé dentro de autocad para crear nuevas heramientas.

Cristian Bastidas

student•

Excelente para complementar mi clase de compiladores

Obed Paz

student•

Otra de forma de llegar a la notacion Pos Fija es ir anotando los operandos (en este caso las letras) en nuestro resultado, y en una stack aparte ir apilando los los parentesis de abre y los operadores, y cuando en la expresion original nos encontremos con un parentesis de cierre, debemos limpiar la pila y sacar los operadores para agregarlos a nuestro resultado:

. Si suena un poco confuso, dejo un ejemplo:

/* Hagamoslo con el ejemplo de la clase: */
[(a + b) / (c * (d - e))]

. Lo que hacemos entonces es que siempre encerramos toda la expresion en llaves, (o en parentesis como quieras). . Reccoremos la expresion y vemos que tenemos una llave y un parentesis que abre, por lo tanto los agregamos a la pila

[(

Continuamos avanzando y vemos que hay una letra, la anotamos en nuestro resultado: a Ahora hay un operador +. Los operadores van a la pila:

[(+

Continuamos avanzando y vemos que hay una letra, la unimos a nuestro resultado:

ab Ahora nos encontramos con un parentesis de cierre, aqui es cuando limpiamos la pila para agregar los operadores a nuestro resultado. ab+ . La primera llave no se saca hasta no llegar a la llave de cierre en la expresion. Por lo tanto, nuestra pila esta solo con la llave de abre. [ Ya recorrimos la primera parte de la expresion: [++(a + b)++ / (c * (d - e))] Vamos con la que queda: --> / (c * (d - e))] . De primera nos encontramos un operando, lo apilamos en nuestra pila: [/ . Luego tenemos un parentesis de abre, lo agregamos: [/( . Lugo hay un operando, este lo unimos a nuestro resultado: ab+c . Y asi sucesivamente hasta llegar a un parentesis de cierre para sacar los operadores de la pila y agregarlos en orden de salida a nuestro resultado: ab+cde-*/

Percival Ernesto Amezola Rivera

student•

Daniel Alejandro Romero

student•

¿Yo siempre he tenido duda de en donde quedaría el valor absoluto en la jerarquía de operaciones?

Milton Martinez

student•

En el video lo pone primero con los paréntesis

Árboles Binarios para Expresiones Aritméticas

Introducción al curso

Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas

Lógica

Lógica Proposicional: Conceptos y Aplicaciones Básicas

Tablas de verdad y conectores lógicos: conjunción, disyunción y más

Construcción de Tablas de Verdad para Proposiciones Compuestas

Construcción de Tablas de Verdad para Proposiciones Lógicas

Tablas de Verdad y Análisis de Proposiciones Lógicas

Circuitos Lógicos: Representación y Función en Electrónica

Circuitos Lógicos para Proposiciones Compuestas

Tablas y Circuitos Lógicos: Ejercicios Prácticos

Teoría de conjuntos

Conjuntos: Definición, Pertenencia y Representación Matemática

Conjuntos: Nulo, Unitario y Universal y Operaciones Básicas

Representación Gráfica de Operaciones entre Conjuntos

Propiedades de los Conjuntos: Leyes de De Morgan y Representación Gráfica

Representación gráfica de las leyes de De Morgan

Operaciones y Propiedades de Conjuntos: Ejercicio Práctico Resuelto

Operaciones Básicas con Conjuntos y Problemas de Conjuntos

Teoría de grafos

Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

Grado de Vértices y Conexiones en Gráficas Simples

Caminos y ciclos eulerianos en grafos: teoría y aplicación

Caminos y Ciclos Hamiltonianos en Grafos

Construcción de Matrices de Adyacencia para Representar Grafos

Representación de Grafos con Matriz de Incidencia

Matrices de Adyacencia en Grafos Dirigidos

Análisis de Caminos y Ciclos Eulerianos en Grafos

Árboles

Árboles y Tipos de Árboles en Matemáticas Discretas

Estructuras de Árboles en Programación y Jerarquías de Datos

Conceptos Básicos de Estructuras de Árboles en Informática

Árbol de Expansión Mínima: Conexión Óptima de Nodos

Tipos de Árboles Binarios y sus Características

Recorridos de Árboles: Preorden, Inorden y Posorden

Árboles Binarios para Expresiones Aritméticas

Transformación de Expresiones Aritméticas en Árboles Binarios

Árboles: Altura, Niveles y Recorridos Ordenados

Algoritmos

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

Algoritmo de Kruskal

Algoritmo de Flury: Encontrar Ciclos Eulerianos en Grafos

Algoritmo de Flujo Máximo en Redes Dirigidas

Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Conclusiones

Repaso Final de Matemáticas Discretas: Lógica, Conjuntos y Algoritmos