首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题

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

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

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

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

abcd(])[efg

输出

false

说明

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

示例2

输入

a[x(y)z]

输出

true

说明

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

算法知识视频讲解

JavaScript

萌萌萌哒

JavaScript(Node) 😎题目:唯品会💄-括号配对问题（stack+flag）

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
rl.on('line', line=>{
    let inArr = line.trim().split(' ')
    let s = inArr[0].split('')
    let stack = []
    let flag = 1
    for (let i = 0; i < s.length; i++) {
        if(s[i] == '[' || s[i] == '('){
            stack.push(s[i])
        }else if(s[i] == ']' || s[i] == ')'){
            if(stack.length === 0){
                flag = 0
                break
            }
            let c = stack[stack.length -1]
            stack.pop()
            if((c == '[' && s[i] != ']') || ( c == '(' && s[i] != ')' )){
                flag  = 0
                break
            }
        }
    }
    if(stack.length !== 0){
        flag = 0
    }
    console.log(flag? 'true' : 'false')
})

发表于 2020-03-01 17:39:19 回复(0)