Validating Parentheses using Go and a Stack Data Structure
Parentheses are a common element in many programming languages, and it's often necessary to check whether a string of parentheses is balanced. In Go, we can use a stack data structure to keep track of the parentheses as we iterate through the string.
The Stack Data Structure
A stack is a last-in, first-out (LIFO) data structure that allows us to push elements onto it and pop them off in a specific order. In our case, we can use a stack to keep track of opening parentheses as we encounter them in the string. When we encounter a closing parenthesis, we can pop the top element off the stack and check if it is the corresponding opening parenthesis.
The Go Code
Here is the Go code that demonstrates how to use a stack to check if a string of parentheses is balanced:
func isValid(s string) bool { // Create a stack to store parentheses stack := make([]byte, 0) // Iterate through the string for i := 0; i < len(s); i++ { // If the current character is an opening parenthesis, push it onto the stack if s[i] == '(' || s[i] == '[' || s[i] == '{' { stack = append(stack, s[i]) } else { // If the stack is empty, the parentheses are not balanced if len(stack) == 0 { return false } // Pop the top element from the stack top := stack[len(stack)-1] stack = stack[:len(stack)-1] // Check if the current character is a closing parenthesis that matches the opening parenthesis on top of the stack if s[i] == ')' && top != '(' || s[i] == ']' && top != '[' || s[i] == '}' && top != '{' { return false } } } // If the stack is not empty, the parentheses are not balanced return len(stack) == 0 }
This function iterates through the string, pushing opening parentheses onto the stack and popping them off when a corresponding closing parenthesis is encountered. At the end, if the stack is empty, the parentheses are balanced. Otherwise, they are not balanced.
Testing the Function
You can use the `isValid` function like this:
fmt.Println(isValid("()")) // Outputs: true fmt.Println(isValid("[{}]")) // Outputs: true fmt.Println(isValid("[{()}]"))
0 Comments