有效括号算法题（Golang实现）-白红宇

有效括号算法题（Golang实现）

阅读量：437 次

发布时间：2019-03-06

本文共 1294 字，大约阅读时间需要 4 分钟。

为了判断给定字符串是否有效括号字符串，我们可以使用栈数据结构来模拟括号匹配过程。以下是详细的步骤：

初始化栈和映射关系：创建一个空栈来存储左括号，并创建一个字典来映射右括号到对应的左括号。

处理空字符串：如果输入字符串为空，直接返回true。

检查字符串长度：如果字符串长度为奇数，返回false，因为无法完全匹配。

遍历字符串：

遇到左括号（{、[、(），将其压入栈。

遇到右括号（}、]、)），检查栈是否为空。如果为空，返回false。

检查栈顶是否是对应的左括号。如果是，弹出栈；否则，返回false。

最终检查栈：遍历结束后，若栈为空，返回true，否则返回false。

以下是用Golang实现的有效括号算法：

package main
import "fmt"
func isValid(s string) bool {
    stack := []byte{}
    my_dick := map[byte]byte{
        ']': '[',
        '}': '{',
        ')': '(',
    }
    s_len := len(s)
    if s_len == 0 {
        return true
    }
    if s_len % 2 != 0 {
        return false
    }
    for i := 0; i < s_len; i++ {
        char := s[i]
        if char == '[' || char == '{' || char == '(' {
            stack = append(stack, char)
        } else {
            if len(stack) == 0 {
                return false
            }
            last := stack[len(stack)-1]
            if my_dick[char] == last {
                stack = stack[:len(stack)-1]
            } else {
                return false
            }
        }
    }
    return len(stack) == 0
}
func main() {
    result := isValid("{[}}")
    fmt.Println(result)
}