Valid Parentheses using Golang

Valid Parentheses using Golang

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("[{()}]"))

Post a Comment

0 Comments