Description
Given a string P consisting of only parentheses and asterisk characters (i.e. 「(」, 「)」 and 「"), you are asked to replace all the asterisk characters in order to get a balanced parenthesis string with the shortest possible length, where you can replace each "」 by one 「(」, or one 「)」, or an empty string 「」.
A parenthesis string S is a string consisting of only parentheses (i.e. 「(」 and 「)」), and is considered balanced if and only if:
● S is an empty string, or
● there exist two balanced parenthesis strings A and B such that S=AB, or
● there exists a balanced parenthesis string C such that S=©.
For instance, 「」, 「()」, 「(())」, 「()()」, 「()(())」 are balanced parenthesis strings.
Due to some notorious technical inability, if there are several solutions with the shortest possible length, then you have to report the smallest possible one in lexicographical order.
For every two different strings A and B of the same length n, we say A is smaller than B in lexicographical order if and only if there exists some integer k such that:
● 1≤k≤n, and
● the first (k−1) characters of A and that of B are exactly the same, and
● the k-th character of A is smaller than that of B.
For instance, 「()(())」 is smaller than 「()()()」, and in this case, k=4.
Input
There are several test cases.
The first line contains an integer T (1≤T≤105), denoting the number of test cases. Then follow all the test cases.
For each test case, the only line contains a string of length n (1≤n≤105), denoting the string P that consists of only parentheses and asterisk characters.
It is guaranteed that the sum of n in all test cases is no larger than 5×106.
Output
For each test case, output in one line 「No solution!」 (without quotes) if no solution exists, or otherwise the smallest possible solution in lexicographical order. Note that the output characters are case-sensitive.
Sample Input
5
*))*)
*(*)*
*)*(*
((***)()((**
Sample Output
No solution!
()
()()
(())()(())
一道特別水的題。考試的時候wa了11發沒過，心態崩了，多虧魏哥哥拯救了我。
題目就是要求我們讓每個括號都成功匹配，並且最後輸出的字串是最短的，並且是字典序最小的。*號可以更改爲‘(’，‘)’，‘’。
這題當時想的時候用了好幾個回圈，誰知道套兩個容器就過了，心態大崩啊。
首先從左往右遍歷整個字串。如果搜到‘*’，則將其下標存入point中（是vector）。如果搜到‘(’，則將其下標存入left中（是stack）。如果搜到‘)’，則先判斷之前有沒有搜到‘(’，若有，則棧頂這個‘(’的下標就直接出棧，如果沒有搜到但是前面搜到過‘*’，所以將這個‘*’的位置改成‘(’即可，然後這個‘*’從point中刪除。若這些條件都不滿足，則說明無法匹配，輸出No solution!。這一段操作的意思就是優先匹配‘)’。
接下來再匹配‘(’，如果point不爲空，並且point尾部的‘*’的下標要大於棧中沒有匹配的‘(’的下標，則說明point尾部的‘*’可以直接更改爲‘)’，然後將這個‘*’的下標從point中刪除，這個‘(’的下標出棧。若這個條件不滿足，則說明無法匹配，輸出No solution!。
最後遍歷一遍輸出兩種括號即可。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<unordered_map>
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e6+10,NN=2e3+10,INF=0x3f3f3f3f,LEN=20;
const ll MOD=1e9+7;
const ull seed=31;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
char str[N];
void init(){
}
int main(){
int t;
t=read();
while(t--){
scanf("%s",str);
bool flag=true;
int len=strlen(str);
stack<int>left;
vector<int>point;
for(int i=0;i<len;i++){
if(str[i]=='*') point.push_back(i);
else if(str[i]=='(') left.push(i);
else{
if(!left.empty()) left.pop();
else if(!point.empty()){
str[point.front()]='(';
point.erase(point.begin());
}
else{
flag=false;
break;
}
}
}
while(!left.empty()){
if(!point.empty()&&(point.back()>left.top())){
str[point.back()]=')';
left.pop();
point.pop_back();
}
else{
flag=false;
break;
}
}
if(!flag) printf("No solution!\n");
else{
for(int i=0;i<len;i++) if(str[i]!='*') printf("%c",str[i]);
puts("");
}
}
}