题目描述
给定一个字符串,由( * )三个字符组成,判断是否满足要求左括号和有括号一一对应,且对应的左括号必定在右括号前面。其中,*可以被当做一个单独的左括号,右括号或者可以当做不存在。
GO代码
// 带*号的小括号表达式匹配
func Test5() {
inputStr := []string{
"()", "*", "(*)", "", "())", "(()", "()()", "(abcd)", "(abc)((ded)",
}
var check func(input string, stack []byte) bool
check = func(input string, stack []byte) bool {
for i := 0; i < len(input); i++ {
switch input[i] {
case '(':
stack = append(stack, input[i])
case ')':
if len(stack) >= 1 && stack[len(stack)-1] == '(' {
stack = stack[:len(stack)-1]
} else {
return false
}
case '*':
// 左括号
r2 := check(input[i+1:], append(stack, '('))
// 右括号
r3 := check(input[i+1:], append(stack, ')'))
if r2 || r3 {
return true
}
// 不成立的话尝试去当做空白字符串
}
}
return len(stack) == 0
}
for i := 0; i < len(inputStr); i++ {
stack := make([]byte, 0, len(inputStr[i]))
fmt.Printf("%s %v", inputStr[i], check(inputStr[i], stack))
}
}
运行结果
