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:

Go
Copy to clipboard
1func AreBracketsBalanced(inputStr string) bool {
2    // pair each opening bracket with its corresponding closing bracket
3    bracketMap := map[rune]rune{
4        '(': ')',
5        '[': ']',
6        '{': '}',
7    }
8
9    // set to identify opening brackets
10    openPar := map[rune]bool{
11        '(': true,
12        '[': true,
13        '{': true,
14    }
15
16    var stack []rune
17
18    // Iterate over each character in the input string
19    for _, char := range inputStr {
20        if openPar[char] { // push onto the stack if opening bracket
21            stack = append(stack, char)
22        } else { // otherwise check for matching opening bracket
23            if len(stack) == 0 || bracketMap[stack[len(stack)-1]] != char {
24                return false // match wasn't found
25            }
26            stack = stack[:len(stack)-1] // match was found
27        }
28    }
29    return len(stack) == 0 // return true if there are no leftovers
30}

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.

Let's reverse the process — literally — by reversing strings. While it might sound simple, it highlights effective data structure usage in programming.

Think about building a function for a user to enter a string, then display the reversed string as part of an application's feature. More complexly, stack buffers in computer networks often reverse packet order. Using a stack to reverse elements in Go, in this case a slice, is immensely useful.

Thanks to the LIFO feature of stacks, implemented using slices in Go, we can easily reverse the order of elements. We push characters to the slice, then pop them out, effectively reversing the input string.

Here's the Go implementation for reversing a string using a slice to simulate stack operations:

Go
Copy to clipboard
1func ReverseString(str string) string {
2    var stack []rune
3
4    for _, char := range str {
5        stack = append(stack, char)
6    }
7
8    var reversed []rune
9    for len(stack) > 0 {
10        n := len(stack) - 1
11        reversed = append(reversed, stack[n])
12        stack = stack[:n]
13    }
14
15    return string(reversed)
16}

The ReverseString function uses a slice to mimic stack operations and efficiently reverse a string:

1. Initialization: Two slices are declared: stack to store the input string's characters and reversed to collect them in reverse order.

2. Stacking Characters: It iterates over the string, appending each character to stack, simulating pushing onto a stack.

3. Unstacking to Reverse: While stack is not empty, it pops the last element (simulating stack behavior) and appends it to reversed. This systematically reverses the order of characters.

4. Output: Once the stack is empty, the reversed slice contains the characters in reverse order, which is converted to a string and returned.

This approach demonstrates the stack's LIFO nature in reversing a sequence.

Today, you've tackled two classical problems using the stack concept to illustrate its practical application in Go. The stack's LIFO nature allowed for ensuring the correctness of nested structures and simply reversing sequences. Congratulations on completing this lesson! The insights gained here prepare you to tackle real-world challenges where operation orders must be preserved or verified for correctness. Happy coding!