Unbalanced String Puzzle

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

Let’s 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 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! The answer is posted below the following test data DDL statements.

```DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString 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; there’s no need to copy both code boxes. The code is pretty simple, and I’ve added comments if any clarification is needed.

```DROP TABLE IF EXISTS ##Match;
GO

CREATE TABLE ##Match
(
RowNumber INT IDENTITY(1,1) PRIMARY KEY,
ExpectedOutcome VARCHAR(50),
MatchString 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,' ',''),

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

--Update the UpdateString column to remove any matching objects
BEGIN
------------------
UPDATE  ##Match
------------------
UPDATE  ##Match
-------------------
UPDATE  ##Match
-------------------

--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!