Algorytm sprawdzania poprawności zagnieżdżenia nawiasów, ...poszukiwany Opcje

[slawa]

Jak w temacie. Poszukuje wszelkich wskazówek jak napisać skrypt który sprawdzał by poprawność zagnieżdżenia nawiasów., mając na wejściu tablicę z kolejnymi nawiasami. Może ktoś się spotkał z takim algorytmem -> prosze o informację

[piczu]

to mi przypomina jedno zadanie z konkursu algorytmicznego
wrzucasz wszystkie nawiasy na stos albo do tablicy i szukasz nawiasu z domknieciem obok siebie, a gdy je znajdziesz to usuwasz i powtarzasz az nic nie zostanie (co oznacza ze wszystkie sa domkniete) lub zostana same niedomkniete. Mam nadzieje ze oto chodzi.

[NuLL]

[PHP] pobierz, plaintext 
<?php
function sprawdzNawiasy($tablica_nawiasow)
{
list($tab1,$tab2)=array_chunk($tablica_nawiasow,count($tablica_nawiasow)/2);
 
$x=current($tab2)
 
foreach($tab1 as $nawias)
{
if($lol==$nawias) return false;
$x=next($tab2);
}
return true;
}
?>
[PHP] pobierz, plaintext 

Jakos tak

[piczu]

a to moja wersja

[PHP] pobierz, plaintext 
<?php
function checkDelimiters($delimiters, $left_delimiter, $right_delimiter) {
	if(is_array($delimiters)) $delimiters = implode("",$delimiters);
	while(preg_match("/".urlencode($left_delimiter.$right_delimiter)."/",urlencode($delimiters))) {
		$delimiters = urldecode(preg_replace("/".urlencode($left_delimiter.$right_delimiter)."/","",urlencode($delimiters)));
	}
	if (strlen($delimiters)) return false;
	return true;
}
 
var_dump( checkDelimiters('((()))','(',')') );
?>
[PHP] pobierz, plaintext 

[LBO]

To i ja się podłączę.

[PHP] pobierz, plaintext 
<?php
/**
 * Funkcja sprawdzająca poprawnośc zagnieżdżenia nawiasów podanych w tablicy
 * $delimiters.
 *
 * @param array $delimiters   Tablica z kolejnymi nawiasami.
 * @return boolean			Zwraca TRUE, jeżeli zagnieżdzenie nawiasów jest
 *							poprawne lub FALSE w przeciwnym razie.
 */
function checkDelimiters($delimiters) {
	// inicjalizacja stosu
	$stack = array();
	foreach ($delimiters as $delimiter) {
		switch ($delimiter) {
			case '(':
				// każdy nawias otwierający kładziemy na stosie
				$stack[] = '(';
				break;
 
			case ')':
				// wykrywa nieprawidłową kolejność nawiasów np. )(())(
				if (array_pop($stack) != '(') {
					return false;
				};
				break;
 
			default:
				print('Błąd, argument nie jest nawiasem'.PHP_EOL);
				return false;
				break;
		};
	};
	if (count($stack) == 0) {
		// jeżeli stos został opróżniony, nawiasy były poprawnie zagnieżdżane.
		return true;
	};
	return false;
};
?>
[PHP] pobierz, plaintext 

edit:
oraz przykład zastosowania.

[PHP] pobierz, plaintext 
<?php
$delimiters = array('(', '(', '(', ')', ')', ')');
var_dump(checkDelimiters($delimiters)); // bool(true)
 
$delimiters = array(')', '(', '(', '(', ')', ')');
var_dump(checkDelimiters($delimiters)); // bool(false)
?>
[PHP] pobierz, plaintext 

Ten post edytował LBO 4.07.2006, 01:24:03

[.radex]

wrzucasz wszystkie nawiasy na stos albo do tablicy i szukasz nawiasu z domknieciem obok siebie, a gdy je znajdziesz to usuwasz i powtarzasz az nic nie zostanie (co oznacza ze wszystkie sa domkniete) lub zostana same niedomkniete.

Też coś dam. Sam do końca nie wiem jak to zrobić, ale wg. tego jak napisał piczu to będzie to wygladało mniej-wiecej tak:

[PHP] pobierz, plaintext 
<?php
function sprawdz( $tablica , $beg , $end ){
 
$begTag = $beg;
$endTag = $end;
 
$tablica1 = explode( ' ' , $tablica ); // usuwamy spacje
 
$tags = $begTag.$endTag ;
 
$tablica2 = explode( $tags , $tablica1 ); // usuwamy ()
 
if ($tablica2 != ''){
$wynik = FALSE ;
}else{
$wynik = TRUE ;
}
?>
[PHP] pobierz, plaintext 

i przykład :

[PHP] pobierz, plaintext 
<?php
include 'function.check.php';
 
sprawdz ( '[[][]][][][' , '[' , ']' );
 
if($wynik = FALSE) { echo 'popraw'; }
?>
[PHP] pobierz, plaintext 

ma to kilka bledow i nie wiem czy by zadzialalo, ale tam...