Programación: Contar paréntesis máquina estados (PHP)

tutorial programacion php

En la carrera (Informática) entre otras cosas te enseñan las máquinas de estados, de Turing, etc. Si no recuerdo mal te enseñan que algunas "tienen memoria" para saber en que estado están y otras no. En la carrera no tuve el placer de programar ninguna máquina de estados y me quedé con las ganas. Un día en el trabajo un compañero y yo discutíamos si era posible con una Expresión Regular averiguar si una cadena de texto tenía los paréntesis cerrados. Tras mucho discutir se me iluminó la luz y entonces recordé que justo este era un caso en el que se necesitaba una máquina de estados "con memoria", no recuerdo como se llamaban ténicamente (era algo como máquina de estados determinista, pero no recuerdo exactamente). En el caso de contar paréntesis con una Expresión regular no es posible saber si los paréntesis abiertos coinciden en número con los cerrados y si además cuando se abre uno, se cierra en el orden correcto.

Algoritmo para comprobar cadena de paréntesis en PHP

Esa noche, mientras intentaba dormirme, mi cabeza no dejaba de darle vueltas al tema de contar parentesis y comprobar si están cerrados correctamente. Como no podía dormir comencé a desarrollar el algoritmo mientras intentaba dormir. Llegó un momento en el que me di cuenta de que no podía terminar el algoritmo en mi cabeza y tampoco iba a poder dormir hasta que no lo programara... Así que me levanté, encendí el ordenador y esto es lo que salió:

<?php

// Si no viene cadena mostramos un formulario para que usuario meta la cadena
if (!$cadena) 
    echo "<form><input type='text' name='cadena'><input type=submit></form>";
else {
	$p = new Parentesis ($cadena);
	$p->analiza();
}

// Clase que gestiona los parentesis
class Parentesis
{ 
    // Cadena que contiene parentesis ej:(a+b)*((a+c)-(a+c+d+(a+d)))
	var $cadena=null;

    // Numero de parentesis que quedan por cerrar
	var $numero=0;

    // Posicion en la que estamos
	var $actual=null;
    // Inicializamos la clase parentesis con la cadena que contiene parentesis
	function Parentesis($cadena)
	{
		$this->cadena=$cadena;
		print "Analizando: ".$this->cadena."<br>";
	}
    // Método recursivo para analizar
	function analiza()
	{
		print "Entramos en analiza con cadena ".$this->cadena." y con numero de parentesis ".$this->numero."<br>";
        // Condicion de salida
		$this->comprueba();

        // Cogemos el primer caracter de la cadena
		$this->actual = substr($this->cadena,0,1);

        // Eliminamos el primer caracter de la cadena
		$this->cadena = substr($this->cadena,1);

        // Comprobamos si es un parentesis (si no es un parentesis se ignora)
		switch ($this->actual){
			case '(':
            // Hay un parenteis abierto
			$this->numero++;
			break;
            // Hay un parentesis cerrado
			case ')':
			$this->numero--;
			break;
		}
        // Llamamos a la misma funcion (recursiva)
		$this->analiza();

	}
    // comprobará la cadena, solo cuando la cadena tenga longitud 0 habremos terminado
	function comprueba()
	{
		if ((strlen($this->cadena)==0)&&($this->numero==0)) {print "correcto";exit;}
		if ((strlen($this->cadena)==0)&&($this->numero!=0)) {print "incorrecto";exit;}
		if ($this->numero<0) {print "incorrecto";exit;}
	}
}

?>

Conclusión de los paréntesis en PHP

Al día siguiente le envié al compañero el programa hecho en PHP que contaba parénteis. Él realmente lo necesitaba en Python, pero como yo no sé Python se lo pasé en PHP por si le servía de ayuda para rehacerlo fácilmente en otro lenguaje de programación.

Creo que el código me quedó limpio, sin ninguna ñapa, asi que estoy contento con él. 

Por motivos obvios no usa librerias ni plantillas (templates), al ser un script php tan sencillo no necesita florituras.

Si habéis llegado aquí por google, espero haberos ayudado a contar paréntesis!

Votos totales: 659