Estructuras de datos - Análisis de expresiones
El análisis de expresiones (parsing expressions) es una de las aplicaciones más clásicas de la estructura de datos pila.
El análisis de expresiones muestra cómo utilizar la pila para manejar la conversión entre expresiones infijas, prefijas y posfijas, así como la evaluación de expresiones.
Tres formas de expresión
Conversión de la expresión infija A + B * C a posfija — demostración paso a paso
Paso 1Leer AOperando, se emite directamenteSalida: APila: vacía
Paso 2Leer +Operador, se apilaSalida: APila: +
Paso 3Leer BOperando, se emite directamenteSalida: ABPila: +
Paso 4Leer *La prioridad de * es mayor que la de +, se apilaSalida: ABPila: +*
Paso 5Leer COperando, se emite directamenteSalida: ABCPila: +*
Paso 6FinDesapilar todos los operadores de la pilaSalida: ABC*+Pila: vacía
Resultado final: A + B * C → A B C * +
Cuando se procesan expresiones matemáticas en una computadora, hay tres formas de representarlas:
| Tipo | Posición del operador | Ejemplo | Dificultad de evaluación | Necesidad de paréntesis |
|---|---|---|---|---|
| Expresión infija | Entre los operandos (habitual para las personas) | A + B * C | Requiere manejar prioridades y paréntesis | Sí |
| Expresión prefija(notación polaca) | Antes de los operandos | + A * B C | Basta con escanear una vez | No |
| Expresión posfija(notación polaca inversa) | Después de los operandos | A B C * + | Basta con escanear una vez | No |
La mayor ventaja de las expresiones posfijas y prefijas es que, durante la evaluación, no es necesario considerar la prioridad de los operadores ni los paréntesis; basta con escanearlas de izquierda a derecha.
Algoritmo de conversión de infijo a posfijo (idea del algoritmo Shunting Yard)
El algoritmo central para convertir una expresión infija en posfija se implementa con ayuda de la pila; el proceso básico es el siguiente:
- Escanea la expresión infija de izquierda a derecha
- Al encontrar unoperando(número/letra), emítelo directamente
- Al encontrar unoperador, compáralo con el operador de la cima de la pila según su prioridad:
- Si el operador en la cima de la pila tiene una prioridad mayor o igual, desapícalo y emítelo
- Repite este proceso hasta que puedas apilar el operador actual
- Al encontrar unparéntesis izquierdo, apícalo directamente
- Al encontrar unparéntesis derecho, desapila y emite repetidamente el operador de la cima hasta encontrar un paréntesis izquierdo (el paréntesis izquierdo se desapila, pero no se emite)
- Al terminar el escaneo, desapila y emite uno a uno los operadores restantes de la pila
Ejemplo
#include <stdio.h>
#include <ctype.h> /* función isalnum */
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
/* Devuelve la prioridad del operador: cuanto mayor es el número, mayor es la prioridad */
int precedence(char op) {
if (op == '+' || op == '-') return 1; /* La suma y la resta tienen la prioridad más baja */
if (op == '*' || op == '/') return 2; /* La multiplicación y la división tienen una prioridad más alta */
if (op == '^') return 3; /* La potenciación tiene la prioridad más alta */
return 0; /* No es un operador */
}
/* Convertir expresión infija a posfija
Parámetros: infix es la cadena de entrada de la expresión infija
postfix es el buffer de salida de la expresión posfija */
void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char c;
while ((c = infix[i++]) != '\0') {
/* Operando (letra o dígito): se emite directamente */
if (isalnum(c)) {
postfix[j++] = c;
}
/* Paréntesis izquierdo: se apila directamente */
else if (c == '(') {
push(c);
}
/* Paréntesis derecho: desapilar hasta encontrar un paréntesis izquierdo */
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
pop(); /* Desapilar el paréntesis izquierdo '(' pero no emitirlo */
}
/* Operador: manejar la prioridad */
else {
while (top != -1 &&
precedence(stack[top]) >= precedence(c) &&
stack[top] != '(') {
postfix[j++] = pop();
}
push(c);
}
}
/* Desapilar todos los operadores restantes de la pila */
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; /* Fin de la cadena */
}
int main() {
char infix[] = "A+B*C";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("infijo: %s\n", infix); /* Salida: infijo: A+B*C */
printf("posfijo: %s\n", postfix); /* Salida: posfijo: ABC*+ */
return 0;
}
#include <ctype.h> /* función isalnum */
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
/* Devuelve la prioridad del operador: cuanto mayor es el número, mayor es la prioridad */
int precedence(char op) {
if (op == '+' || op == '-') return 1; /* La suma y la resta tienen la prioridad más baja */
if (op == '*' || op == '/') return 2; /* La multiplicación y la división tienen una prioridad más alta */
if (op == '^') return 3; /* La potenciación tiene la prioridad más alta */
return 0; /* No es un operador */
}
/* Convertir expresión infija a posfija
Parámetros: infix es la cadena de entrada de la expresión infija
postfix es el buffer de salida de la expresión posfija */
void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char c;
while ((c = infix[i++]) != '\0') {
/* Operando (letra o dígito): se emite directamente */
if (isalnum(c)) {
postfix[j++] = c;
}
/* Paréntesis izquierdo: se apila directamente */
else if (c == '(') {
push(c);
}
/* Paréntesis derecho: desapilar hasta encontrar un paréntesis izquierdo */
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
pop(); /* Desapilar el paréntesis izquierdo '(' pero no emitirlo */
}
/* Operador: manejar la prioridad */
else {
while (top != -1 &&
precedence(stack[top]) >= precedence(c) &&
stack[top] != '(') {
postfix[j++] = pop();
}
push(c);
}
}
/* Desapilar todos los operadores restantes de la pila */
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; /* Fin de la cadena */
}
int main() {
char infix[] = "A+B*C";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("infijo: %s\n", infix); /* Salida: infijo: A+B*C */
printf("posfijo: %s\n", postfix); /* Salida: posfijo: ABC*+ */
return 0;
}
Evaluación de expresiones posfijas
Evaluación de la expresión posfija 5 3 + 2 * — demostración paso a paso
Paso 1Leer 5Número, se apilaPila: 5
Paso 2Leer 3Número, se apilaPila: 5 3
Paso 3Leer +Desapilar 3 y 5, calcular 5+3=8, apilar el resultadoPila: 85+3=8
Paso 4Leer 2Número, se apilaPila: 8 2
Paso 5Leer *Desapilar 2 y 8, calcular 8*2=16, apilar el resultadoPila: 168*2=16
ResultadoFinEn la pila solo queda 16, que es el resultado del cálculoResultado = 16
La expresión posfija 53+2* = 16 (equivalente a la infija (5+3)*2)
Una vez que se tiene la expresión posfija, evaluarla con la pila es muy directo: al encontrar un operando, se apila; al encontrar un operador, se desapilan dos operandos, se calcula y se apila el resultado.
Ejemplo
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
/* Calcular el valor de una expresión posfija
Parámetros: postfix es la expresión posfija (los operandos son dígitos individuales 0-9)
Valor de retorno: el resultado del cálculo de la expresión */
int evaluatePostfix(char* postfix) {
int i = 0;
char c;
while ((c = postfix[i++]) != '\0') {
/* Operando: convertir a número y apilar */
if (isdigit(c)) {
push(c - '0'); /* '3' se convierte al entero 3 */
}
/* Operador: desapilar dos operandos, calcular y volver a apilar */
else {
int b = pop(); /* Segundo operando (operando derecho) */
int a = pop(); /* Primer operando (operando izquierdo) */
switch (c) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop(); /* El último elemento de la pila es el resultado final */
}
int main() {
/* La expresión posfija "23+5*" equivale a la expresión infija "(2+3)*5" = 25 */
char postfix[] = "23+5*";
int result = evaluatePostfix(postfix);
printf("posfijo %s = %d\n", postfix, result); /* Salida: posfijo 23+5* = 25 */
return 0;
}
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
/* Calcular el valor de una expresión posfija
Parámetros: postfix es la expresión posfija (los operandos son dígitos individuales 0-9)
Valor de retorno: el resultado del cálculo de la expresión */
int evaluatePostfix(char* postfix) {
int i = 0;
char c;
while ((c = postfix[i++]) != '\0') {
/* Operando: convertir a número y apilar */
if (isdigit(c)) {
push(c - '0'); /* '3' se convierte al entero 3 */
}
/* Operador: desapilar dos operandos, calcular y volver a apilar */
else {
int b = pop(); /* Segundo operando (operando derecho) */
int a = pop(); /* Primer operando (operando izquierdo) */
switch (c) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop(); /* El último elemento de la pila es el resultado final */
}
int main() {
/* La expresión posfija "23+5*" equivale a la expresión infija "(2+3)*5" = 25 */
char postfix[] = "23+5*";
int result = evaluatePostfix(postfix);
printf("posfijo %s = %d\n", postfix, result); /* Salida: posfijo 23+5* = 25 */
return 0;
}
Al evaluar una expresión posfija, el orden en que se desapilan los operandos es fundamental: el primero en desapilarse es eloperando derecho(b); el segundo en desapilarse es eloperando izquierdo(a). Esto es especialmente importante para operaciones no conmutativas, como la resta y la división; invertir el orden producirá un resultado incorrecto.
Ejemplo completo: evaluación de una expresión infija
Al combinar los dos pasos anteriores se puede implementar una calculadora completa: infijo → posfijo → evaluación.
Ejemplo
#include <stdio.h>
#include <ctype.h>
#define MAX 100
/* Función auxiliar de prioridad de operadores (igual que antes), función de evaluación (igual que antes), función de conversión (igual que antes) */
/* Por brevedad, se omiten aquí las funciones ya definidas; en la práctica hay que incluirlas */
int main() {
char infix[] = "5+3*2"; /* Expresión infija */
char postfix[MAX];
infixToPostfix(infix, postfix); /* Paso 1: convertir a posfija */
printf("infijo: %s\n", infix); /* Salida: infijo: 5+3*2 */
printf("posfijo: %s\n", postfix); /* Salida: posfijo: 532*+ */
int result = evaluatePostfix(postfix); /* Paso 2: evaluar */
printf("resultado: %s = %d\n", infix, result);
/* Salida: resultado: 5+3*2 = 11 */
return 0;
}
#include <ctype.h>
#define MAX 100
/* Función auxiliar de prioridad de operadores (igual que antes), función de evaluación (igual que antes), función de conversión (igual que antes) */
/* Por brevedad, se omiten aquí las funciones ya definidas; en la práctica hay que incluirlas */
int main() {
char infix[] = "5+3*2"; /* Expresión infija */
char postfix[MAX];
infixToPostfix(infix, postfix); /* Paso 1: convertir a posfija */
printf("infijo: %s\n", infix); /* Salida: infijo: 5+3*2 */
printf("posfijo: %s\n", postfix); /* Salida: posfijo: 532*+ */
int result = evaluatePostfix(postfix); /* Paso 2: evaluar */
printf("resultado: %s = %d\n", infix, result);
/* Salida: resultado: 5+3*2 = 11 */
return 0;
}