Posted on by Kalkicode
Code Greedy

Minimum swaps for bracket balancing in java

Java program for Minimum swaps for bracket balancing. Here more information.

import java.util.ArrayList;
/*
    Java program for
    Minimum swaps for bracket balancing
*/
public class Balancing
{
    public void swapBalancingCount(String text)
    {
        int n = text.length();
        if (n == 0)
        {
            return;
        }
        // Auxiliary variables
        int bracketCount = 0;
        int index = 0;
        long sum = 0;
        char[] data = text.toCharArray();
        // This is collecting the all open bracket character position.
        ArrayList < Integer > openBracket = new ArrayList < Integer > ();
        // This loop are collecting position of all open bracket.
        // And calculates the number of open and close brackets.
        for (int i = 0; i < n; ++i)
        {
            if (data[i] == '[')
            {
                openBracket.add(i);
                bracketCount++;
            }
            else
            {
                bracketCount--;
            }
        }
        if (bracketCount != 0)
        {
            // Means open and close brackets not same
            return;
        }
        // Reset bracket counter
        bracketCount = 0;
        for (int 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.get(index) - i);
                // Swap element
                char t = data[i];
                data[i] = data[openBracket.get(index)];
                data[openBracket.get(index)] = t;
                // Reset counter
                bracketCount = 1;
                // Position to next open bracket
                index++;
            }
        }
        // Balancing bracket
        String ans = new String(data);
        // Display given and calculated results
        System.out.println(" Given text     : " + text);
        System.out.println(" Results text   : " + ans);
        System.out.println(" Swaps  : " + sum);
    }
    public static void main(String[] args)
    {
        Balancing task = new Balancing();
        String 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);
    }
}

// Minimum swaps for bracket balancing
// minimum-swaps-bracket-balancing

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