Using Stacks in Go for Balancing Parentheses and Reversing Strings

Welcome back! Today, we further explore stack operations in Go. Our session today involves using the last-in, first-out principle to address two problems that will enhance your understanding of stack operations.

In computing, validating nested structures such as parentheses is imperative, much like ensuring boxes are correctly nested within one another. We'll craft a function to verify that a string of parentheses is properly nested and closed, essentially checking for balance.

Improperly balanced parentheses can introduce errors in programming, similar to missing or misplaced pieces in a puzzle. Our function will serve as a meticulous checker, ensuring each opened parenthesis is correctly closed.

In Go, a stack can be efficiently implemented using slices. Though Go lacks a built-in stack type, the LIFO (Last In, First Out) principle can be emulated using slices to track the order of opening and closing brackets — in which the most recently opened bracket must be closed first — ensuring balanced parentheses.

Using Go, we'll set up a map to pair each opening bracket with its corresponding closing bracket and use a slice to simulate stack operations. We could also use the Stack structure that we built earlier, using the Pop, Push and Peak methods. We are leveraging a slice for simplicity.

We iterate over each character in the string: If it's an opening bracket, we append it to the slice. If it's a closing bracket, we check if the slice's top element matches; if so, we remove it.

If a mismatched closing bracket is found, or if there are unmatched opening brackets at the end, the function returns false.

Here's how we implement this in Go:

func AreBracketsBalanced(inputStr string) bool {
    // pair each opening bracket with its corresponding closing bracket
    bracketMap := map[rune]rune{
        '(': ')',
        '[': ']',
        '{': '}',
    }

    // set to identify opening brackets
    openPar := map[rune]bool{
        '(': true,
        '[': true,
        '{': true,
    }

    var stack []rune

    // Iterate over each character in the input string
    for _, char := range inputStr {
        if openPar[char] { // push onto the stack if opening bracket
            stack = append(stack, char)
        } else { // otherwise check for matching opening bracket
            if len(stack) == 0 || bracketMap[stack[len(stack)-1]] != char {
                return false // match wasn't found
            }
            stack = stack[:len(stack)-1] // match was found
        }
    }
    return len(stack) == 0 // return true if there are no leftovers
}

The function returns false under these conditions:

1. A closing bracket is found without a matching opening bracket.
2. Unmatched opening brackets remain in the stack at the end.