(栈)有效的括号


给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

代码如下

package main

import "log"

func isValid(s string) bool {
	// 获取字符串长度
	n := len(s)
	// 判断长度是否为偶数,如果不是直接返回false
	if n%2 == 1 {
		return false
	}
	// map映射,用判断我们的括号是否是成对的
	p := map[byte]byte{
		']': '[',
		')': '(',
		'}': '{',
	}
	// 我们初始化一个栈
	stack := *new([]byte)
	// 下面我们开始遍历字符串
	for i := 0; i < n; i++ {
		if p[s[i]] > 0 { // 这里说明有可以匹配的括号,我们要进行判断
			// 首先要确保栈的长度大于0,并且当前字符的map映射和栈顶是对应的,否则就直接返回false
			if len(stack) == 0 || stack[len(stack)-1] != p[s[i]] {
				return false
			}
			// 这里我们进行出栈操作
			stack = stack[:len(stack)-1]
		} else { // 这里说明没有匹配括号,我们这里进行入栈操作
			stack = append(stack, s[i])
		}
	}
	// 判断栈是否为空,如果为空说明括号是匹配的
	return len(stack) == 0

}

func main() {
	log.Println(isValid("()[]{"))
}

代码相对比较简单,我们这里直接用栈来进行操作,看代码就可以直观的看出来,这里就不再详解


文章作者: 小游
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 小游 !
  目录