WJG (21/12/18) I needed a quick and simple way of checking whether or not brackets and braces were 'balanced' in a paragraph of text. Ok, this is usually the sort of thing needed in programming but, for my purposes this to trap potential formatting issues in a text processor. So, I guess this example could be used for testing embedded quotations too, clarifying problems such as ' " " ', or ' " " ', depending on one's writing style. Any comments and/or optimizations most welcome.
set str "a((bc)) \{de\{f\} ghi"
# unbalanced { before de
## Check string for balanced brackets and braces.
# This method uses 2 stacks rather than 1.
# stack1 contains a list of opening characters
# stack2 keeps a list of the string indices of the the opening bracket or brace
# Rather than returning a true or false value, the proc returns the
# location of the imbalance to better suit the needs of editing with a GUI
#
#/param str the string to be tested
#/returns index of imbalance or empty string, ie {}
#
# https://www.youtube.com/watch?v=QZOLb0xHB_Q
#
proc balance { str } {
set idx 0
set stack2 {}
foreach c [split $str ""] {
switch $c {
"(" -
"\{" -
"\[" {
lappend stack1 $c
lappend stack2 $idx
}
")" -
"\}" -
"\]" {
set p [lindex $stack1 end]
if { [string first $p "(\{\["] >= 0 } {
set stack1 [lrange $stack1 0 end-1]
set stack2 [lrange $stack2 0 end-1]
} else {
return $idx
}
}
}
incr idx
}
return [lindex $stack2 end]
}
set idx [balance $str]
# insert caret to mark out identified imbalance in the bracketing
if { $idx ne ""} { puts [string range $str 0 $idx-1]^[string range $str $idx end] }
Running the above snippet writes the following to the console:
a((bc)) ^{de{f} ghikpv - 2018-12-21 23:10:15
Couldn't help adding another approach using regular expressions. The idea is to first remove everything but braces, then repeatedly delete all matching braces. If the result is empty then the braces must have balanced. With a bit of cleverness, you can use the same approach and report the location of all mis-balanced braces.
proc isBalanced {str} {
# Return true if str has balanced braces
regsub -all {[^\[\]\{\}()]} $str "" x
while {[regsub -all {\{\}|\[\]|\(\)} $x "" x]} continue
return [expr {$x eq ""}]
}
proc re_balance {str} {
# Return a list of locations of mis-balanced braces, empty list if balanced
regsub -all {[^\[\]\{\}()]} $str "_" x
while {[regsub -all {\{(_*)\}|\[(_*)\]|\((_*)\)} $x {\1\2\3} x]} continue
return [lmap idx [regexp -all -indices -inline {[\[\]\{\}()]} $x] {lindex $idx 0}]
}