Skip to main content

Minimum swaps for bracket balancing in golang

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

package main

import "fmt"
/*
    Go program for
    Minimum swaps for bracket balancing
*/
func swapBalancingCount(text string) {
	var n int = len(text)
	if n == 0 {
		return
	}
	// Auxiliary variables
	var bracketCount int = 0
	var index int = 0
	var sum int = 0
	var data = text
	var point = 0
	// This is collecting the all open bracket character position.
	var openBracket = make([]int,0)
	// 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] == '[' {
			openBracket = append(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)
			point = openBracket[index]
			// Swap element
			var t byte = data[i]
			
			data = data[:i] +  string(data[point]) + data[i+1:]
			data = data[:point] + string(t) + data[point+1:]


			// Reset counter
			bracketCount = 1
			// Position to next open bracket
			index++
		}
	}
	// Balancing bracket

	// Display given and calculated results
	fmt.Println(" Given text     : ", text)
	fmt.Println(" Results text   : ", data)
	fmt.Println(" Swaps  : ", sum)
}
func main() {

	var text string = "]]][[[[]"
	/*
	    ]]][[[[]  <-  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
	*/
	swapBalancingCount(text)
	text = "][[][]"
	/*
	    ][[][]  <-  text
	      -- 
	    [][][]  ➀ Swap position 0-1

	    ----------------------------
	    Number of swap : 1
	*/
	swapBalancingCount(text)
}

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