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), 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; 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), 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!