匹配括号问题

匹配括号问题

给定一个只包括"（","）","[","]","{","}"组成的字符串，判断字符串中的括号是否全部有效。

括号全部有效的字符串需要满足：

1，左括号必须用相同类型的右括号闭合

2，左括号必须以正确的顺序闭合。

注意：空字符串可以被认为是有效的。

例1：输入 ”()“，输出 True

例2：输入 ”[()]{}“,输出 True

例3：输入 ”[(])[]“ 输出 False

例4：输入 "[({})][]" 输出 true

题目思路

要满足 括号闭合的条件, 可以通过栈 来实现,
首先遍历字符串
如果遇到左边的括号,就入栈.
如果遇到右边的括号 就弹出栈顶元素. 看是不是匹配.如果匹配,就继续 遍历字符串.
如果不匹配 ,就直接返回False 就可以了.

遍历完成后,如果栈中 没有元素了, 说明完全匹配了.就返回True
如果栈中还有元素, 说明 还有元素没有匹配, 返回 False.

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
@User    : frank 
@Time    : 2019/7/23 20:30
@File    : day0723.py
@Email  : frank.chang@xinyongfei.cn
给定一个只包括"（","）","[","]","{","}"组成的字符串，判断字符串中的括号是否全部有效。
括号全部有效的字符串需要满足：
1，左括号必须用相同类型的右括号闭合
2，左括号必须以正确的顺序闭合。
注意：空字符串可以被认为是有效的。
例1：输入 ”()“，输出 True
例2：输入 ”[()]{}“,输出 True
例3：输入 ”[(])[]“ 输出 False
"""
class Stack:
    """模拟栈
    Stack()    建立一个空的栈对象
    push()     把一个元素添加到栈的最顶层
    pop()      删除栈最顶层的元素，并返回这个元素
    peek()     返回最顶层的元素，并不删除它
    is_empty()  判断栈是否为空
    size()     返回栈中元素的个数
    """
    def __init__(self):
        self.items = []
        self._size = len(self.items)
    def print_stack(self):
        for item in self.items:
            print(item, end=' ')
    def is_empty(self):
        return self.size == 0
    def push(self, item):
        self.items.append(item)
        self._size += 1
    def pop(self):
        if self.size == 0:
            raise IndexError("stack is empty now.")
        self._size -= 1
        return self.items.pop()
    def peek(self):
        if not self.is_empty():
            return self.items[len(self.items) - 1]
    @property
    def size(self):
        return self._size
class Solution:
    left = {"{", "(", "["}
    right = {"}", ")", "]"}
    stack = Stack()
    def is_pipei(self, string):
        for char in string:
            if char in self.left:
                self.stack.push(char)
            else:
                top = self.stack.pop()
                if self.match(top, char):
                    continue
                else:
                    return False
        return True
    def match(self, char1, char2):
        """
        判断是否匹配
        :return: bool
        """
        d = {"[": "]", "{": "}", "(": ")"}
        if char1 in d:
            return d[char1] == char2
        return False
if __name__ == '__main__':
    solution = Solution()
    print(solution.is_pipei("[]"))
    print(solution.is_pipei("[[]]"))
    print(solution.is_pipei("[()]{}"))
    print(solution.is_pipei("[({})]"))
    print(solution.is_pipei("[(])[]"))  # false
    print(solution.is_pipei("[()]("))   # false
    pass