Unbalanced String Puzzle

Here is a fun puzzle that I was recently challenged with. Here we need to determine if a string is balanced if there is a matching opening and closing parenthesis, bracket or brace. Not only does the string need to have a matching parenthesis, bracket or brace, but the matching object also needs to be in the correct order.

Lets look at a few examples.

The following three would be considered balanced as they have the objects in the correct order.

( ( { [] } ) )
( ) [ ]
( { } )

The following three would not match as the objects are not in the correct order
( { ) }
( { ) } } } ( )
} { ( ) ] [

Can you figure out the trick to easily determine if the string is balanced?

Here is some quick test data, just hit the copy button in the upper right of the box.

Spoiler alert, below the test data I will post the answer.

DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString VARCHAR(50),
UpdateString VARCHAR(50)
);
GO

INSERT INTO ##Match (ExpectedOutcome, MatchString) VALUES
('Balanced','( )'),
('Balanced','[]'),
('Balanced','{}'),
('Balanced','( ( { [] } ) )'),
('Balanced','( ) [ ]'),
('Balanced','( { } )'),
('Unbalanced','( { ) }'),
('Unbalanced','( { ) }}}()'),
('Unbalanced','}{()][');
GO

Here is the answer to the puzzle. I’ve also included the table population statements as well, no need to copy both of the code boxes. The code is pretty simple and I’ve added comments if there is any clarification needed.

DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString VARCHAR(50),
UpdateString VARCHAR(50)
);
GO

INSERT INTO ##Match (ExpectedOutcome, MatchString) VALUES
('Balanced','( )'),
('Balanced','[]'),
('Balanced','{}'),
('Balanced','( ( { [] } ) )'),
('Balanced','( ) [ ]'),
('Balanced','( { } )'),
('Unbalanced','( { ) }'),
('Unbalanced','( { ) }}}()'),
('Unbalanced','}{()][');
GO

--Remove any spaces
--Populates the column UpdateString that we will manipulate with the below UPDATE statements
UPDATE ##Match
SET MatchString = REPLACE(MatchString,' ',''),
    UpdateString = REPLACE(MatchString,' ','');

--Set a Loop Counter
DECLARE @vLoop INTEGER = 1;
WHILE @vLoop <> 0

    --Update the UpdateString column to remove any matching objects
    BEGIN
    ------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'()','');
    ------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'[]','');
    -------------------
    UPDATE  ##Match
    SET UpdateString = REPLACE(UpdateString,'{}','');
    -------------------

    --Determine if there are any more matching objects to update
    WITH cte_Charindex AS
    (
    SELECT CHARINDEX('()',UpdateString) AS LoopDetermine FROM ##Match
    UNION
    SELECT CHARINDEX('[]',UpdateString) AS LoopDetermine FROM ##Match
    UNION
    SELECT CHARINDEX('{}',UpdateString) AS LoopDetermine FROM ##Match
    )
    SELECT @vLoop = MAX(LoopDetermine) FROM cte_Charindex;
    -------------------

    END;

--If the UpdateString column is empty, then it is a balanced string 
SELECT  *, CASE WHEN UpdateString = '' THEN 'Balanced' ELSE 'Unbalanced' END AS FinalResult 
FROM    ##Match;

Note that this solution requires an iterative based solution rather than a set-based solution. Although set-based solutions are generally preferred, this is a good example of when to use an iterative based solution to arrive at your answer.

Happy coding!