HDU 6799 Parentheses Matching (2020 항 저 우 다 교 훈련 3 차 전)
항주 전기 OJ 6799
Problem 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=(C).
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! () ()()
(())()(())
간단 한 데이터 구 조 를 바탕 으로 대열 의 선진 적 인 선 출 과 스 택 의 선진 적 인 선 출 만 사용 하 는 원칙 은 괄호 의 일치 문제 입 니 다. 우 리 는 왼쪽 에서 오른쪽으로 일치 한 다음 에 오른쪽 에서 왼쪽으로 일치 하면 됩 니 다. 대열 q 로 앞에서 읽 은 '*', 스 택 k 저장 괄호 (왼쪽 에서 오른쪽으로 저장 '(', 오른쪽 에서 왼쪽으로 저장 ') 를 저장 합 니 다.... 매번 순환 할 때마다 대기 열 과 스 택 을 비 워 야 합 니 다.
#include
#define rep(i,a,b) for(int i=a;i
#define T int t ;cin >> t;while(t--)
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-11;
const ll mod = 1e9 + 7;
queue<int> q ;
stack<int> k ;
int main()
{
int t ;
cin >> t ;
while(t--)
{
int flag = 1 ;
char a[maxn] ;
scanf("%s",a) ;
while(!q.empty())
q.pop();
while(!k.empty())
k.pop();
ll xlen = strlen(a) ;
ll high = 0 , low = 0 ;
for(int i = 0 ; i < xlen ; i++)
{
if(a[i] == '(')
k.push(i) ;
if(a[i] == '*')
q.push(i) ;
if(a[i] == ')')
{
if(k.size())
{
k.pop();
}
else
{
if(!q.empty())
{
int xx=q.front();
q.pop();
a[xx]='(';
}
else
flag = 0 ;
}
}
}
if(!flag)
{
printf("No solution!
");
continue;
}
while(!q.empty())
q.pop();
while(!k.empty())
k.pop();
for(int i = xlen-1 ; i >= 0 ; i--)
{
if(a[i] == ')')
k.push(i) ;
else if(a[i] == '*')
q.push(i) ;
else if(a[i] == '(')
{
if(k.size())
{
k.pop() ;
}
else
{
if(!q.empty())
{
int xx=q.front();
q.pop();
a[xx]=')';
}
else
flag = 0 ;
}
}
}
if(!flag&&k.empty())
printf("No solution!
") ;
else
{
for(int i = 0 ; i < xlen ; i++)
{
if(a[i]!='*')
printf("%c",a[i]) ;
}
printf("
") ;
}
}
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode - 503. 다음 더 큰 요소 II (Next Greater Element II) [중간] - 분석 및 코드 (Java)순환 배열 (마지막 요소 의 다음 요 소 는 배열 의 첫 번 째 요소) 을 지정 하고 모든 요소 의 다음 요 소 를 출력 합 니 다.숫자 x 의 다음 더 큰 요 소 는 배열 에 따라 순 서 를 옮 겨 다 니 는 것 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.