Go 和 PHP 判断有效括号

Go 和 PHP 判断有效括号

author: he xiaodong date: 2020-04-23

原文链接: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