Version 1 of Testing for Balanced Brackets and Braces.

Updated 2018-12-21 12:45:31 by WJG

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
        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} ghi