首页 > 试题广场 >

缺失的括号

[编程题]缺失的括号
  • 热度指数：111 时间限制：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
算法知识视频讲解
添加回答
mu_luo头像 mu_luo
就挺简单的 
#include <iostream>
using namespace std;
int main() {
    char c;
    int left = 0, right = 0;
    while (cin >> c) {
        if (c == '(')
            left++;
        else if (c == ')') {
            if (left > 0)
            left--;
            else right++;
        }
            
    }
    cout << left + right;
    return 0;
 
}


发表于 2021-07-31 19:08:21 回复(0)
huanghj头像 huanghj 

	//遇到匹配的就出栈，剩下的即为需要匹配的





	#include <iostream>





	#include <stack>





	#include <string>





	 





	usingnamespacestd;





	 





	intmain(){





	    stack<char> s;





	    string str;





	    cin>>str;





	    intn=str.size();





	    for(inti=0;i<n;++i){





	        if(s.empty())





	            s.push(str[i]);





	        elseif(s.top()=='('&&str[i]==')')





	            s.pop();





	        else





	            s.push(str[i]);





	    }





	    cout<<s.size()<<endl;





	     





	    return0;





	}

发表于 2018-01-07 16:34:48 回复(0)
zjwzjw369头像 zjwzjw369 

	#include<iostream>





	#include<vector>





	#include<algorithm>





	#include<cmath>





	#include<stack>





	usingnamespacestd;





	 





	intmain(){





	    string s;





	    cin>>s;





	    stack<char> sk;





	    intans=0;





	    for(inti=0;i<s.length();++i){





	        if(s[i]=='('){





	            sk.push(s[i]);





	        }else{





	            if(!sk.empty()){





	                sk.pop();





	                ans+=2;





	            }





	        }





	    }





	    cout<<s.length()-ans<<endl;





	    return0;





	}
先找配置的括号，然后总长度减去匹配括号的长度就是结果。
发表于 2017-12-16 18:08:12 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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