Google 面试题：有效括号字符串

题目描述

给定一个字符串，由（ * ）三个字符组成，判断是否满足要求左括号和有括号一一对应，且对应的左括号必定在右括号前面。其中，*可以被当做一个单独的左括号，右括号或者可以当做不存在。

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))
	}
}

运行结果