首页 > 试题广场 >

缺失的括号

[编程题]缺失的括号
  • 热度指数：6040 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串，那么(s)也是完整的。
3、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()(" 和 ")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

输入描述:
输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50).
s中每个字符都是左括号或者右括号,即'('或者')'.


输出描述:
输出一个整数,表示最少需要添加的括号数
示例1

输入

(()(()

输出

2
算法知识视频讲解
添加回答
Python
Re:煙花ゼロから易冷头像 Re:煙花ゼロから易冷 
s = input()
left = 0
right = 0
for i in s:
    if i == '(':
        left += 1
    else:
        if left > 0:
            left -= 1
        else:
            right +=1
print(left+right)

发表于 2019-04-16 15:15:28 回复(0)
Python
fighting@SHU头像 fighting@SHU
aa=input()

lenth=len(aa)

k=0

count=0

for i in range(lenth):

    if(aa[i]== '(' ):

    k=k+1

elif((aa[i]== ')')&(k>0)):

    k=k-1

else:

    count=count+1

k=k+count

print(k)

Count多余的右括号，K记录多余的左括号；
发表于 2019-03-19 11:41:14 回复(0)
Python
华科平凡头像 华科平凡

python解法

a = input()
arr, res = [], 0
for i in a:
    if i == "(":  # 如果为左括号，直接扔进arr数组
        arr.append("(")
    else: # 此时为右括号
        if len(arr) > 0: # 如果有匹配的左括号，将arr中消除掉一个左括号。
            arr.pop(-1)
        else: #此时没有匹配的左括号，要手动添加一个。
            res += 1
print(res + len(arr)) # 最后结果还要加上数组中左括号的个数，因为要额外添加对应数量的右括号
发表于 2019-03-02 14:21:32 回复(0)
Python
兰偷荀令香头像 兰偷荀令香
input_str = input().strip()
lst = []
num = 0
for i in input_str:
    if i == '(':
        lst.append(i)
    elif i == ')':
        if lst:
            lst = lst[: -1]
        else:
            num += 1
print(num + len(lst))
发表于 2019-02-19 15:52:15 回复(0)
提交观点

问题信息

贪心 字符串 模拟 栈 算法工程师 爱奇艺 2018
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
5条回答 8181浏览

热门推荐

通过挑战的用户

查看代码

相关试题

缺失的括号

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号