2020-04-23-Go和PHP判断有效括号

layout: posttitle: Go 和 PHP 判断有效括号
subtitle: Go 和 PHP 判断有效括号
date: 2020-04-23
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 有效括号

原文链接：go leetcode，php 代码个人原创

有效括号（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
}

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

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券