Estructura de datos: análisis de expresiones

La forma de escribir una expresión aritmética se conoce como notation. Una expresión aritmética se puede escribir en tres notaciones diferentes pero equivalentes, es decir, sin cambiar la esencia o la salida de una expresión. Estas notaciones son:

• Notación infija
• Notación de prefijo (polaco)
• Notación de sufijo (polaco inverso)

Estas notaciones se denominan según la forma en que usan el operador en la expresión. Aprenderemos lo mismo aquí en este capítulo.

Notación infija

Escribimos expresión en infix notación, por ejemplo, a - b + c, donde se utilizan operadores in-entre operandos. Es fácil para nosotros, los humanos, leer, escribir y hablar en notación infija, pero lo mismo no va bien con los dispositivos informáticos. Un algoritmo para procesar la notación infija podría ser difícil y costoso en términos de consumo de tiempo y espacio.

Notación de prefijo

En esta notación, el operador es prefixed a operandos, es decir, el operador se escribe antes que los operandos. Por ejemplo,+ab. Esto es equivalente a su notación infijaa + b. La notación de prefijo también se conoce comoPolish Notation.

Notación de sufijo

Este estilo de notación se conoce como Reversed Polish Notation. En este estilo de notación, el operador espostfixed a los operandos, es decir, el operador se escribe después de los operandos. Por ejemplo,ab+. Esto es equivalente a su notación infijaa + b.

La siguiente tabla trata de mostrar brevemente la diferencia en las tres notaciones:

No Señor.	Notación infija	Notación de prefijo	Notación de sufijo
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Analizar expresiones

Como hemos comentado, no es una forma muy eficiente de diseñar un algoritmo o programa para analizar notaciones infijas. En cambio, estas notaciones infijas se convierten primero en notaciones sufijas o prefijas y luego se calculan.

Para analizar cualquier expresión aritmética, también debemos tener en cuenta la precedencia de los operadores y la asociatividad.

Precedencia

Cuando un operando está entre dos operadores diferentes, qué operador tomará el operando primero, se decide por la precedencia de un operador sobre otros. Por ejemplo

Como la operación de multiplicación tiene prioridad sobre la suma, primero se evaluará b * c. Más adelante se proporciona una tabla de precedencia de operadores.

Asociatividad

La asociatividad describe la regla en la que los operadores con la misma precedencia aparecen en una expresión. Por ejemplo, en la expresión a + b - c, tanto + como - tienen la misma precedencia, entonces qué parte de la expresión se evaluará primero, está determinada por la asociatividad de esos operadores. Aquí, tanto + como - son asociativos a la izquierda, por lo que la expresión se evaluará como(a + b) − c.

La precedencia y la asociatividad determinan el orden de evaluación de una expresión. A continuación se muestra una tabla de precedencia y asociatividad de operadores (de mayor a menor):

No Señor.	Operador	Precedencia	Asociatividad
1	Exponenciación ^	Más alto	Asociativo derecho
2	Multiplicación (∗) y división (/)	Segundo más alto	Asociativo izquierdo
3	Suma (+) y resta (-)	Más bajo	Asociativo izquierdo

La tabla anterior muestra el comportamiento predeterminado de los operadores. En cualquier momento de la evaluación de la expresión, el orden se puede modificar utilizando paréntesis. Por ejemplo

En a + b*c, la parte de expresión b*cse evaluará primero, con la multiplicación como precedente sobre la suma. Aquí usamos paréntesis paraa + b para ser evaluado primero, como (a + b)*c.

Algoritmo de evaluación de postfijo

Ahora veremos el algoritmo sobre cómo evaluar la notación postfija:

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Para ver la implementación en lenguaje de programación C, haga clic aquí .