首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题

热度指数：7952 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个字符串 $S$ ，请检查字符串中仅由括号字符 `[`、`]`、`(`、`)` 组成的子序列是否构成合法括号序列。合法括号序列的定义如下：

$\hspace{23pt}\bullet\,$ 空序列是合法括号序列；

$\hspace{23pt}\bullet\,$ 如果 $A$ 是合法括号序列，则 `(A)` 和 `[A]` 都是合法括号序列；

$\hspace{23pt}\bullet\,$ 如果 $A$ 和 $B$ 都是合法括号序列，则它们的拼接 $AB$ 也是合法括号序列。

$\hspace{15pt}$ 字符串 $S$ 可能包含其他字符，但只需考虑括号部分，忽略其他字符。

输入描述:

在一行中输入一个字符串 ，长度 ，由可见字符组成。

输出描述:

如果字符串  中的括号部分能构成合法括号序列，则输出 `true`；否则输出 `false`。

示例1

输入

abcd(])[efg

输出

false

说明

提取括号 `(`、`)`、`[`、`]` 后为 `(])[`，不是合法括号序列。

示例2

输入

a[x(y)z]

输出

true

说明

提取括号后为 `[()]`，是合法括号序列。

算法知识视频讲解

Python

贾志统

class My_Stack:
    def __init__(self, elements=[]):
        self._elements = list(elements)
    
    def is_empty(self):
        #return not self._elements 
        return self._elements == []
    
    def push(self, element):
        self._elements.append(element)
    
    def pop(self):
        if self.is_empty():
            raise ValueError
        element = self._elements.pop()
        return element


def func(input_str):
    st = My_Stack()
    for ch in input_str:
        if ch == "[" or ch == "(":
            st.push(ch)
        elif ch == "]":
            if st.is_empty():
                print("false")
                return
            element = st.pop()
            if element != "[":
                print("false")
                return
        elif ch == ")":
            if st.is_empty():
                print("false")
                return
            element = st.pop()
            if element != "(":
                print("false")
                return
        else:
            continue
    if not st.is_empty():
        print("false")
    else:
        print("true")

        
input_str = input()
func(input_str)

发表于 2019-08-30 23:47:59 回复(0)

Python

ElonB

""""
括号匹配，借助栈后进先出的性质
"""

if __name__ == "__main__":
    s = input().strip()
    ans = True
    flag = []
    for c in s:
        if c == '[' or c == '(':
            flag.append(c)
        elif c == ']':
            if not flag or flag.pop() != '[':
                ans = False
                break
        elif c == ')':
            if not flag or flag.pop() != '(':
                ans = False
                break
        else:
            pass
    if flag:
        ans = False
    print("true" if ans else "false")

编辑于 2019-07-12 11:22:20 回复(0)