Member Avatar for kingben

Hi. Please refer the code.
I am having trouble in the 3 times nested loop (at the end)

<?php
	error_reporting(E_ALL);
	ini_set('display_errors', true);
	ini_set('html_errors', true);
	function remove_blank_spaces($strWhite) {
		trim($strWhite);
		$string = "";
		for($i=0; $i<strlen($strWhite); $i++) {
			if($strWhite[$i]!=" ") {
				$string .= $strWhite[$i];
			}
		}
		return $string;
	}
	function get_all_substrings($input, $delim='') {
		$arr = explode($delim,$input);
		for($i=0 ; $i<count($arr) ; $i++) {
			for($j=$i ; $j<count($arr) ; $j++) {
				$out1[] = implode($delim, array_slice($arr,$i,$j-$i+1));
				$outi[] = $i;
				$outj[] = $j+1;
			}
		}
		foreach ($out1 as $value) {
			$out[] = remove_blank_spaces($value);
		}
		$final[count($out)][3] = array();
		for($i=0 ; $i<count($out) ; $i++) {
			for($j=0 ; $j<3 ; $j++) {
				if($j==0)
					$final[$i][$j] = $out[$i];
				else if($j==1)
					$final[$i][$j] = $outi[$i];
				else if($j==2)
					$final[$i][$j] = $outj[$i];
			}
		}
		return $final;
	}
?>
<html>
	<head>
		<title>CYK Algorithm</title>
	</head>
			<body>		
		<?php
		if(!$_POST['submit'] == "Submit") {	//If no Data submitted
		?>
			<form action="cyk.php" method="post">
				<h1>Enter Non Terminals of Grammar</h1><br/>
				<textarea name="nonterminals" rows="10" cols="50"></textarea><br/>
				<h1>Enter Terminals of G</h1><br/>
				<textarea name="terminals" rows="10" cols="50"></textarea><br/>
				<h1>Enter Productions of Grammar in CNF</h1><br/>
				<textarea name="grammar" rows="10" cols="50"></textarea><br/>
				<h1>Enter String to be tested</h1><br/>
				<input type="text" name="string"><br/>
				<h1></h1>
				<input type="submit" value="Submit" name="submit">
			</form>	
		<?php
		}
		else {	//If Data submitted
			$string = "";
			for($i=0 ; $i<strlen($_POST['string']) ; $i++) {
				$string .= $i;
				$string .= $_POST['string'][$i];
			}
			$string .= strlen($_POST['string']); //$string contains 0a1b2a3b4
			
			$nonterminals = explode("\n",$_POST['nonterminals']);
			$terminals = explode("\n",$_POST['terminals']);
			$grammar = explode("\n",$_POST['grammar']);
			$matrix [strlen($_POST['string'])][strlen($_POST['string'])] = array();
			for($i=0; $i<strlen($_POST['string']) ; $i++)
				for($j=0; $j<strlen($_POST['string']) ; $j++)
					$matrix[$i][$j] = 0;
			
			$strings = "";
			for($i=0 ; $i<strlen($_POST['string']) ; $i++) {
				$strings .= $_POST['string'][$i];
				$strings .= " ";
			}
			//$strings contains "a b a b"
			$subs = get_all_substrings(trim($strings)," ");
			//$subs is an array of all the substrings of a given string
				//format: substring - i - j
			$RHS = array();
			$LHS = array();
			foreach ($grammar as $value)
				list($LHS[], $RHS[]) = explode('->', trim($value));
			//to do : for every substring, if that substring is in RHS, insert the corresponding LHS to i,j of substring
			
			for($i=0; $i<(count($subs)-1) ; $i++) {
				if(in_array($subs[$i][0],$RHS)) {
					$key = array_search($subs[$i][0],$RHS);
					$matrix[$subs[$i][1]][$subs[$i][2]-1] = $LHS[$key];
				}
			}
			
			
			for ($j=2; $j<strlen($_POST['string']); $j++) {
				for ($i=$j-1; $i==1; $i--) {
					for ($h=$i; $h<$j-1; $h++) {
						$counter = 0;
						foreach ($RHS as $value) {
							if(strlen($value)>1) {
								if(($matrix[$i][$h] == $value[0]) && ($matrix[$h+1][$j] == $value[1])) {
									$matrix[$i][$j] .= $LHS[$counter];
								}
						}
							$counter++;
						}
					}
				}
			}
		
				echo "<br/>";
			
			for($i=0; $i<strlen($_POST['string']) ; $i++) {
				for($j=0; $j<strlen($_POST['string']) ; $j++) {
					echo $matrix[$i][$j];
					echo "&nbsp;";
				}
					echo "<br/>";
			}
			
			
			
		}
		?>			
			</body>
</html>

please help me out

Without a better description of the issue, all we can do is guess.

I'm guessing the second loop, starting on Line 103 and controlled by $i, isn't running because of the exit condition you've specified. It only runs if $i == 1. Is this the correct condition? Based on the surrounding code, I have my doubts.

Member Avatar for kingben

Without a better description of the issue, all we can do is guess.

I'm guessing the second loop, starting on Line 103 and controlled by $i, isn't running because of the exit condition you've specified. It only runs if $i == 1. Is this the correct condition? Based on the surrounding code, I have my doubts.

Yeah ... that shouldn't be ==.
I was just testing around with trial and error with the loop and have pasted one of those tests.... i have also tried other conditions .... here's how the algo works:
http://blog.redmoonit.de/?p=229

wikipedia also has more details.

can you help ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.