Created by [CecilWesterhof].

During in an interview I got a question about how to implement checking if a string containing brackets was valid.

For example the following are valid:
======
"{()}"
"{\[()]}"
"{{\[\[(())]]}}"
======

And the following is invalid:
======
"{\[(])}"
======

I implemented that in Java, but  found it interesting to try it in Tcl. It saves some work.

I kept it relatively simple. For example if the stack contains more elements as the rest of the string contains, you know the complete string is not valid. (I implemented this in the Java version, but thought it made the code a little harder to read, without a significant gain.)

The implementation:
======
proc balancedBrackets {string} {
    if {[expr {[string length $string] % 2}]} {
        return 0
    }
    set stack {}

    foreach ch [split ${string} {}] {
        switch -- ${ch} {
            \( {
                lappend stack \)
            }
            \[ {
                lappend stack \]
            }
            \{ {
                lappend stack \}
            }
            \) -
            \] -
            \} {
                if {[lindex ${stack} end] ne ${ch}} {
                    return 0
                }
                set stack [lrange ${stack} 0 end-1]
            }
            default {
                error "Wrong character: ${ch}"
            }
        }
    }
    return [expr {[llength ${stack}] == 0}]
}
======

The following code:
======
puts [balancedBrackets "{()}"]
puts [balancedBrackets "{\[()]}"]
puts [balancedBrackets "{{\[\[(())]]}}"]
puts [balancedBrackets "{\[(])}"]
======

gives:
======
1
1
1
0
======

I wanted the brackets to be a parameter. For example it could be nice to have the possibility to add < as opening bracket, with > as corresponding  close bracket. For this I changed it to:
======
proc balancedBrackets {string brackets} {
    if {[expr {[string length $string] % 2}]} {
        return 0
    }
    if {! [isDictKeysValsUnique ${brackets}]} {
        error "Got wrong brackets dict: ${brackets}"
    }
    foreach {bracket} ${brackets} {
        if {[string length ${bracket}] != 1} {
            error "All brackets need to have a length of 1 (${brackets})"
        }
    }
    set closeBrackets [dict values ${brackets}]
    set stack         {}

    foreach ch [split ${string} {}] {
        if {[dict exists ${brackets} ${ch}]} {
            lappend stack [dict get ${brackets} ${ch}]
        } elseif {${ch} in ${closeBrackets}} {
            if {[lindex ${stack} end] ne ${ch}} {
                return 0
            }
            set stack [lrange ${stack} 0 end-1]
        } else {
            error "Wrong character: ${ch}"
        }
    }
    return [expr {[llength ${stack}] == 0}]
}
======

The proc isDictKeysValsUnique is defined [isDict%|%here%|%].

I tested it with:
======
set brackets  [dict create \{ } \[ \] ( )]
set brackets2 [dict create \{ } \[ \] ( ) < >]
puts "Correct strings:"
puts [balancedBrackets "()"               ${brackets}]
puts [balancedBrackets "\[]"              ${brackets}]
puts [balancedBrackets "{}"               ${brackets}]
puts [balancedBrackets "{()}"             ${brackets}]
puts [balancedBrackets "{\[()]}"          ${brackets}]
puts [balancedBrackets "{{\[\[(())]]}}"   ${brackets}]
puts [balancedBrackets "{{\[()\[{}]]}}"   ${brackets}]
puts [balancedBrackets "{{\[()\[{<>}]]}}" ${brackets2}]
puts ""
puts "Wrong strings:"
puts [balancedBrackets "{\[(])}"          ${brackets}]
puts [balancedBrackets "{{\[()\[{<}>]]}}" ${brackets2}]
======

And got the expected output.

Probably to be continued, because there are still a few changes I think that could be interesting.

----

As always: comments, tips and questions are appreciated.


[PYK] 2018-07-22:  What is the definition of "valid string" for this exercise?  If the definition is just that brackets always occur in open/close pairs, this routine suffices: 

======
proc valid value {
    expr {[llength [regexp -all -inline {\[} $value]] == [
        llength [regexp -all -inline {\]} $value]]}
}

puts [list hey [valid "{()}"]]
======

If the definition is "both brackets and braces occur in open/close pairs", the
routine is only slightly different: 


======
proc valid value {
    expr {[llength [regexp -all -inline {[[\{]} $value]] == [
        llength [regexp -all -inline {[]\}]} $value]]}
}
======

If the definition is "brackets and braces and parenthesis must occur in nested
open/close pairs", this routines works:

======
proc valid value {
    while {
        [regsub -all {\([^\{\(\[\)]*?\)|\{[^\{\(\[\}]*?\}|\[[^]\{\(\[]*?\]} $value {} value]
    } {
    }
    return [expr {![regexp {[[\]\(\)\{\}]} $value]}]
}
======

[CecilWesterhof] 2018-07-22: There is a problem with Emacs, because that thinks that the braces do not match. But the code runs, so the braces match.

The string "<>" is seen as correct, but should give an error.

I find my code much more clear (something I find important) and I will change it to a variant where the opening and closing braces will be giving by a dict.

<<categories>>Example