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 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.
I like to get a bit more information as only true or false. That is why I rewrote the proc again. A string is valid if the function returns -1. Any other value means the string was not valid.
# -1 when balanced
# 0 - n-1 index where a wrong closing bracket is found
# -2 when uneven
# -3 when not balanced when string is consumed
# ILLEGAL:c:x illegal character and index where it is found
proc balancedBrackets {string brackets} {
if {[expr {[string length $string] % 2}]} {
return -2
}
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 {}
set index 0
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 $index
}
set stack [lrange $stack 0 end-1]
} else {
return "ILLEGAL:$ch:$index"
}
incr index
}
if {[expr {[llength $stack] == 0}]} {
return -1
} else {
return -3
}
}And 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 "{\[(])}" $brackets]
puts [balancedBrackets "<>" $brackets]
puts [balancedBrackets "{{" $brackets]
puts [balancedBrackets "{{\[()\[{<}>]]}}" $brackets2]I get expected:
Correct strings: -1 -1 -1 -1 -1 -1 -1 -1 Wrong strings: -2 3 ILLEGAL:<:0 -3 8
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.