给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
栈。遍历字符串,遇到左括号,入栈;遇到右括号,出栈。如果中途栈的元素个数小于0;或者遍历完成,栈还有元素;或者元素不匹配,就返回false,否则返回true。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := isValid("{[]()}")
fmt.Println(ret)
}
func isValid(s string) bool {
if len(s) == 0 {
return true
}
str := []byte(s)
N := len(str)
stack := make([]byte, N)
size := 0
for i := 0; i < N; i++ {
cha := str[i]
if cha == '(' || cha == '[' || cha == '{' {
stack[size] = twoSelectOne(cha == '(', ')', (twoSelectOne(cha == '[', ']', '}')))
size++
} else {
if size == 0 {
return false
}
size--
last := stack[size]
if cha != last {
return false
}
}
}
return size == 0
}
func twoSelectOne(c bool, a byte, b byte) byte {
if c {
return a
} else {
return b
}
}
执行结果如下: