Validando paréntesis en una cadena
Como se sabe, los paréntesis se utilizan para agrupar elementos, o para modificar la prioridad en una evaluación. Y como es bien sabido, cuando se tienen muchos paréntesis, se pueden omitir algunos que abren o cierran al momento de generar una cadena que los utilice (como al programar en LISP por ejemplo).
El evaluar los paréntesis en una expresión arimética es usado habitualmente como ejemplo, para explicar el uso de una estructura de datos simple, llamado pila.
La pila solo se le pueden agregar elementos nuevos por un solo lado, llamado el tope y para trabajar con ella, ésta tiene dos operaciones básicas, push para poner un nuevo elemento en el tope de la pila. y pop para extraer el último elemento del tope de la pila.
Aunque teóricamente se pueden apilar elementos hasta el infinito, dado que no existe un límite para el tope, en la práctica estamos limitados por el método de implementación y lugar donde se realiza. Particularmente, en una computadora, el límite de la pila esta marcado por la cantidad de memoria que se puede utilizar para la pila. Por ello existen tres elementos más que describen a una pila: un indicador de principio de pila, un indicador de tope actual y un indicador del límite máximo de la pila.
El indicador actual se incrementa si se hace un push, y se decrementa si se hace un pop. Y por supuesto, debe marcar un error cuando se esta en la base en donde el principio de pila es igual a indicador actual; lo que significa que la pila esta vaciá y se desea extraer un elemento (se marca underflow). De igual forma si el indicador actual es igual a límite máximo de la pila, que significa que estamos en el límite máximo, y se desea agregar un nuevo elemento se debe marcar un error (overflow).
Para evaluar la concordancia de paréntesis en una expresión mediante una pila, lo que se hace es un push a la pila con un "(" cada vez que se encuentra en la expresión, y se hace un pop por cada ")" encontrado.
Después de recorrer toda la expresión que contiene paréntesis, si los paréntesis están correctos, la pila debe terminar vacía. En caso de que exista algún problema de concordancia de paréntesis, aparecerá un underflow si hay más paréntesis que cierran de los que abren, o la pila no estará vacía si es lo opuesto.
Esto es muy útil para estudiar la estructura de datos pila, pero en mi caso simplemente usé un contador: se incrementa por cada paréntesis que abre, y se decrementa por cada paréntesis que cierra. Al final devuelve 0 si hay igual número de paréntesis que abren y cierran. Devuelve -1 si encuentra en algún momento un paréntesis que cierra sin haber encontrado previamente uno que abre y > 0 si hay más paréntesis que abren de los que cierran.
El código implementado como una función en lenguaje C lo pueden ver en:
http://wiki.lidsol.net/wiki/index.php?title=Contando_par%C3%A9ntesis
A continuación coloco el código:
El evaluar los paréntesis en una expresión arimética es usado habitualmente como ejemplo, para explicar el uso de una estructura de datos simple, llamado pila.
La pila solo se le pueden agregar elementos nuevos por un solo lado, llamado el tope y para trabajar con ella, ésta tiene dos operaciones básicas, push para poner un nuevo elemento en el tope de la pila. y pop para extraer el último elemento del tope de la pila.
Aunque teóricamente se pueden apilar elementos hasta el infinito, dado que no existe un límite para el tope, en la práctica estamos limitados por el método de implementación y lugar donde se realiza. Particularmente, en una computadora, el límite de la pila esta marcado por la cantidad de memoria que se puede utilizar para la pila. Por ello existen tres elementos más que describen a una pila: un indicador de principio de pila, un indicador de tope actual y un indicador del límite máximo de la pila.
El indicador actual se incrementa si se hace un push, y se decrementa si se hace un pop. Y por supuesto, debe marcar un error cuando se esta en la base en donde el principio de pila es igual a indicador actual; lo que significa que la pila esta vaciá y se desea extraer un elemento (se marca underflow). De igual forma si el indicador actual es igual a límite máximo de la pila, que significa que estamos en el límite máximo, y se desea agregar un nuevo elemento se debe marcar un error (overflow).
Para evaluar la concordancia de paréntesis en una expresión mediante una pila, lo que se hace es un push a la pila con un "(" cada vez que se encuentra en la expresión, y se hace un pop por cada ")" encontrado.
Después de recorrer toda la expresión que contiene paréntesis, si los paréntesis están correctos, la pila debe terminar vacía. En caso de que exista algún problema de concordancia de paréntesis, aparecerá un underflow si hay más paréntesis que cierran de los que abren, o la pila no estará vacía si es lo opuesto.
Esto es muy útil para estudiar la estructura de datos pila, pero en mi caso simplemente usé un contador: se incrementa por cada paréntesis que abre, y se decrementa por cada paréntesis que cierra. Al final devuelve 0 si hay igual número de paréntesis que abren y cierran. Devuelve -1 si encuentra en algún momento un paréntesis que cierra sin haber encontrado previamente uno que abre y > 0 si hay más paréntesis que abren de los que cierran.
El código implementado como una función en lenguaje C lo pueden ver en:
http://wiki.lidsol.net/wiki/index.php?title=Contando_par%C3%A9ntesis
A continuación coloco el código:
int cta_parents(char* cadena){
int cta=0;
for(;*cadena; cadena++){
if('('==*cadena)
cta++;
else if( ')' ==*cadena){
cta--;
if(cta<0)
return(cta);
}
}
return(cta);
}
Etiquetas: programando
publicadas por César a la/s
1:27 p.m.
1 Comentarios
