有效括号（Valid-Parentheses）
题干如下：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
来源：力扣
解题思路
这题是我大学老师教 栈 这种数据结构的应用场景时讲解的题目，稍微有一丢丢怀念。
解题思路很简单：从左到右遍历字符串，遇到 左括号: [ ( { 就压入栈中，遇到 右括号: ] ) } 就拿 栈顶元素 与 当前元素 匹配，是否是一对括号。是，则继续遍历，不是，则直接返回 false。
注：
1. 栈 是一种很常见的数据结构，特点是先进后出
2. 栈顶元素 每次比较之后都要从栈中移除，即 pop 操作
3. 为什么是遇到 左括号 将其压入栈中呢？假设我们将 右括号 压入栈中，由于我们是从左往右遍历的，当遇到 左括号 时假设我们取出栈顶元素 右括号 进行比较，这时候有一个问题：当前比较的 左括号 的位置其实是在 右括号 之后的，即类似 ][。
聪明的小伙伴一定猜到了，当我们从右向左遍历时，压入栈的就是 右括号 啦。
流程图如下：
代码实现
由于需要基于 栈 这种数据结构来解题，我简单用 go 实现了一个栈：
type Stack struct {
stack []byte // 存放字节
length int // 内部维护的长度
}
// 压栈
func (s *Stack) push(b byte) {
s.stack = append(s.stack,b)
s.length ++
}
// 出栈
func (s *Stack) pop() (res byte) {
if s.length <= 0 {
return
}
s.length --
res = s.stack[s.length]
s.stack = s.stack[0:s.length]
return
}
// 判断栈是否为空
func (s *Stack) isEmpty() bool {
return s.length <= 0
}
// 构造
func getStack() *Stack {
return &Stack{
}
}下面的代码实现，基于上面的数据结构：
func isValid(s string) bool {
if len(s) <= 0 {
return true
}
// 实例化栈
stack := getStack()
for i := 0; i < len(s); i++ {
// 判断是左括号就压入栈
if s[i] == '(' || s[i] == '[' || s[i] == '{' {
stack.push(s[i])
} else {
// 如果栈为空，这时候 i 没有越界，则返回 false
if stack.isEmpty() {
return false
}
// 获取栈顶元素
top := stack.pop()
// 比较是否匹配
if '(' == top && s[i] != ')' || '[' == top && s[i] !=']' || '{' == top && s[i] !='}'{
return false
}
}
}
// 如果 i 越界，并且 栈 为空，则返回 true
if stack.isEmpty() {
return true
}
return false
}扩展思路
在用 栈 解题的过程中会发现： 如果字符串是有效括号，那么一
定存在一对相邻的括号，并且第一个匹配的右括号，左边的元素一定是
相对应的左括号。
基于上面的认知，我们将这对相邻的括号替换成空字符串，剩下的字符串，如果是有效字符串，仍会存在一对相邻的括号，同理再替换，依次循环。如果不存在一对相邻的括号，并且最后剩下的字符串为空了，那么原始字符串就是有效括号，否则不是。
流程图如下：
具体的代码实现如下：（ 只是提供一种思路，这种实现方式时间复杂度有点高 ）
func isValidOther(s string) bool {
// 判断是否有一对相邻的括号
for strings.Index(s,"()") != -1 || strings.Index(s,"[]") != -1 || strings.Index(s,"{}") != -1 {
// 存在，则替换成 空字符串， 继续下次判断
s = strings.Replace(s,"()","",-1)
s = strings.Replace(s,"[]","",-1)
s = strings.Replace(s,"{}","",-1)
}
// 如果不存在一对相邻的括号，并且剩余的字符串长度不为0，则返回 false
if len(s) >= 1 {
return false
}
return true
}总结
每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-algorithm
有疑问加站长微信联系（非本文作者）
