Posted on by Kalkicode
Code Greedy

Minimum swaps for bracket balancing in php

Php program for Minimum swaps for bracket balancing. Here problem description and other solutions.

<?php
/*
    Php program for
    Minimum swaps for bracket balancing
*/
class Balancing
{
	public	function swapBalancingCount($text)
	{
		$n = strlen($text);
		if ($n == 0)
		{
			return;
		}
		// Auxiliary variables
		$bracketCount = 0;
		$index = 0;
		$sum = 0;
		$data = $text;
		// This is collecting the all open bracket character position.
		$openBracket = array();
		// This loop are collecting position of all open bracket.
		// And calculates the number of open and close brackets.
		for ($i = 0; $i < $n; ++$i)
		{
			if ($data[$i] == '[')
			{
				array_push($openBracket, $i);
				$bracketCount++;
			}
			else
			{
				$bracketCount--;
			}
		}
		if ($bracketCount != 0)
		{
			// Means open and close brackets not same
			return;
		}
		// Reset bracket counter
		$bracketCount = 0;
		for ($i = 0; $i < $n; ++$i)
		{
			if ($data[$i] == '[')
			{
				$bracketCount++;
				$index++;
			}
			else if ($data[$i] == ']')
			{
				$bracketCount--;
			}
			if ($bracketCount < 0)
			{
				// Calculate number of swap operations
				// required to move to block brackets.
				// Here open break position will use
				$sum += ($openBracket[$index] - $i);
				// Swap element
				$t = $data[$i];
				$data[$i] = $data[$openBracket[$index]];
				$data[$openBracket[$index]] = $t;
				// Reset counter
				$bracketCount = 1;
				// Position to next open bracket
				$index++;
			}
		}
		// Display given and calculated results
		echo " Given text     : ".$text, "\n";
		echo " Results text   : ".$data, "\n";
		echo " Swaps  : ".strval($sum), "\n";
	}
	public static
	function main($args)
	{
		$task = new Balancing();
		$text = "]]][[[[]";
		/*
		    ]]][[[[]  <-  text
		      -- 
		    ]][][[[]  ➀ Swap position 2-3
		     --
		    ][]][[[]  ➁ Swap position 1-2
		    --
		    []]][[[]  ➂ Swap position 0-1
		       --
		    []][][[]  ➃ Swap position 3-4
		      --
		    [][]][[]  ➄ Swap position 2-3
		        --
		    [][][][]  ➅ Swap position 4-5
		    ----------------------------
		    Number of swap : 6
		*/
		$task->swapBalancingCount($text);
		$text = "][[][]";
		/*
		    ][[][]  <-  text
		    -- 
		    [][][]  ➀ Swap position (0,1)
		    ----------------------------
		    Number of swap : 1
		*/
		$task->swapBalancingCount($text);
	}
}
Balancing::main(array());

Output

 Given text     : ]]][[[[]
 Results text   : [][][][]
 Swaps  : 6
 Given text     : ][[][]
 Results text   : [][][]
 Swaps  : 1

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment