题目描述
定义如下规则:
- 空串是「平衡括号序列」
- 若字符串 S 是「平衡括号序列」,那么[S] 和(S) 也都是「平衡括号序列」
- 若字符串 A 和 B 都是「平衡括号序列」,那么 AB(两字符串拼接起来)也是「平衡括号序列」。
例如,下面的字符串都是平衡括号序列:
()
,[]
,(())
,([])
,()[]
,()[()]
而以下几个则不是:
(
,[
,]
,)(
,())
,([()
现在,给定一个仅由 (
,)
,[
,]
构成的字符串 s,请你按照如下的方式给字符串中每个字符配对:
- 从左到右扫描整个字符串。
- 对于当前的字符,如果它是一个右括号,考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应(即小括号匹配小括号,中括号匹配中括号),则将二者配对。如果左侧未匹配的左括号不存在或与之不对应,则其配对失败。
配对结束后,对于 s 中全部未配对的括号,请你在其旁边添加一个字符,使得该括号和新加的括号匹配。
输入格式
输入只有一行一个字符串,表示 s。
输出格式
输出一行一个字符串表示你的答案。
输入输出样例
输入 #1
([()
输出 #1
()[]()
输入 #2
([)
输出 #2
()[]()
说明/提示
数据规模与约定
对于全部的测试点,保证 s 的长度不超过 100,且只含 (
,)
,[
,]
四个字符。
题解
这道题需要用到栈来解决。首先输入一串字符串,计算字符串的长度n。用for循环来判断括号序列是否平衡。当a[i]为]时,如果此时为空栈,那么继续,如果栈顶是[,那么在数组b中b[i]=b[y](u=x.top())等于1。然后出栈。当a[i]为)时,如果此时为空栈,那么继续,如果栈顶是(,那么在数组b中b[i]=b[y](u=x.top())等于1。然后出栈。如果a[i]为(或是[,那么就将它入栈。
经过一遍for循环后,再用一遍for循环来输出。当b[i]等于1,那么输出a[i],当b[i]不等于1时,当a[i]为(,那么输出(),当a[i]为[时,那么输出[].
代码
#include <iostream> #include <stack> using namespace std; stack <int> x; int main() { string a; cin>>a; int i,n,y,b[1000]={0}; n=a.length(); for(i=0;i<n;i++) { if(a[i]==']') { if(x.empty()) continue; y=x.top(); if(a[y]=='[') { b[y]=b[i]=1; x.pop(); } } else if(a[i]==')') { if(x.empty()) continue; y=x.top(); if(a[y]=='(') { b[y]=b[i]=1; x.pop(); } } else x.push(i); } for(i=0;i<n;i++) { if(b[i]==1) cout<<a[i]; else { if(a[i]=='('||a[i]==')') { cout<<"()"; } else cout<<"[]"; } } return 0; }