原文链接：go leetcode，php 代码个人原创
有效括号（Valid-Parentheses）
题干如下：
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 1.左括号必须用相同类型的右括号闭合。 2.左括号必须以正确的顺序闭合。 3.注意空字符串可被认为是有效字符串。 示例 1: 输入: “()” 输出: true 示例 2: 输入: “()[]{}” 输出: true 示例 3: 输入: “(]” 输出: false 示例 4: 输入: “([)]” 输出: false 示例 5: 输入: “{[]}” 输出: true 来源：力扣
解题思路
这题是我大学老师教 栈 这种数据结构的应用场景时讲解的题目，稍微有一丢丢怀念:smile:。 解题思路很简单：从左到右遍历字符串，遇到 左括号: [ ( { ** 就压入栈中，遇到 **右括号: ] ) } 就拿 栈顶元素 与 当前元素 匹配，是否是一对括号。是，则继续遍历，不是，则直接返回 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
}
PHP 实现：
// 思路和以上一样
function isValid($str) {
$length = strlen($str);
if ($length <= 0) {
return 1;
}
$stack = new SplStack();
for ($i = 0; $i < $length; $i++) {
if (in_array($str[$i], ['(', '[', '{'])) {
$stack->push($str[$i]);
} else {
if ($stack->isEmpty()) {
return 0;
}
$top = $stack->pop();
if ($top === '(' && $str[$i] !== ')' || $top === '[' && $str[$i] !== ']' || $top === '{' && $str[$i] !== '}') {
return 0;
}
}
}
if ($stack->isEmpty()) {
return 1;
}
return 0;
}
echo isValid('()[]{}'); // ouput: 1
echo isValid('[(])'); // ouput: 0
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
