Click the blue text
Follow Zhao Majiang
Luogu Problem Set Link
https://www.luogu.com.cn/training/113#problems
(Copy to your browser to open)
Bracket Sequence
Problem Description
Algorithm Analysis
The original problem did not provide a pairing method, only a description related to “balanced bracket sequences,” but the problem statement was unclear, and later a specific pairing method was added.
First, we need to understand the problem: the string contains only four characters: ‘(‘, ‘)’, ‘[‘, ‘]’, which are two types of brackets. Our task is to find a matching left bracket for each right bracket by searching to the left.
If we find a left bracket that has already been matched, we continue searching left;
If we find an unmatched left bracket, we need to determine if the two brackets are a pair: if they are a pair, it proves that the two brackets match successfully; if they are not a pair, the match fails.
Regardless of success or failure, each right bracket will only undergo one matching judgment.
Finally, when outputting, for all unmatched brackets, ‘(‘ and ‘)’ need to be replaced with “()”, and ‘[‘ and ‘]’ need to be replaced with “[]”.
Once the problem is clear, we can use a simulation algorithm to simulate the entire process, defining an array a[] to record whether each character in the string is matched successfully.
The time complexity of the algorithm is O(n^2). (n is the length of the string)
[Code Display]
#include<iostream>using namespace std; string s; int a[105]; // Used to record whether each bracket in the string is matched int main(){ cin>>s; for(int i=0;i<s.size();i++){ if(s[i]==')'){ // If it's a right bracket, search left for the first unmatched left bracket for(int j=i-1;j>=0;j--){ if(s[j]=='(' && a[j]==0){ // If they match, mark as matched a[i]=a[j]=1; // Mark as matched break; } else if(s[j]=='[' && a[j]==0){ // Otherwise, match fails break; } } } else if(s[i]==']'){ // The same here for(int j=i-1;j>=0;j--){ if(s[j]=='[' && a[j]==0){ a[j]=a[i]=1; break; } else if(s[j]=='('&& a[j]==0){ break; } } } } for(int i=0;i<s.size();i++){ if(a[i]==1) cout<<s[i]; // If matched, output as is else{ // If not matched, supplement with a complete pair of brackets if(s[i]=='(' || s[i]==')')cout<<"()"; else cout<<"[]"; } } return 0;}(Swipe left and right to view the complete code)
[Evaluation Results]
This problem involves bracket matching, and readers sensitive to this type of problem should think of using a stack to store brackets.
When traversing all characters in the string, if it is a left bracket, push it onto the stack;
If it is a right bracket, try to match it with the top element of the stack: if matched successfully, mark it and pop from the stack; if matching fails, do nothing.
Since we use a stack to store left brackets, we eliminate the need to search left for a left bracket, reducing the time complexity of the algorithm to O(n).
[Code Display]
#include<iostream>#include<stack>using namespace std; string s; int a[105]; // Used to record whether each bracket in the string is matched stack<int> st; // Used to store left brackets int main(){ cin>>s; for(int i=0;i<s.size();i++){ if(s[i]==')'){ if(st.empty()) continue; // If the stack is empty, there is nothing to match int j=st.top(); if(s[j]=='('){ a[i]=a[j]=1; st.pop(); } } else if(s[i]==']'){ if(st.empty()) continue; int j=st.top(); if(s[j]=='['){ a[i]=a[j]=1; st.pop(); } } else{ // Otherwise, it's a left bracket, push onto the stack st.push(i); // Note that the position of the left bracket is pushed onto the stack } } for(int i=0;i<s.size();i++){ if(a[i]==1) cout<<s[i]; else{ if(s[i]=='(' || s[i]==')')cout<<"()"; else cout<<"[]"; } } return 0;}(Swipe left and right to view the complete code)
[Evaluation Results]
[Validation of Stack Sequence]Problem Description
Algorithm Analysis
The problem is very simple: given an input stack order and an output stack order, determine whether the output order is valid, i.e., whether it is possible to empty the stack by popping elements in the given order.
Here we need to first record the two sequences (denoted as arrays a[] and b[]) because we will use them alternately.
After recording, we use the STL stack to define a stack, pushing elements onto the stack in the input order, but we also need to perform some operations after each element is pushed.
We need to record what the next element to be popped is, starting with b[0]. If b[0] is equal to the top element of the stack, we need to pop one element from the stack and check if b[1] needs to be popped next.
Therefore, in the code implementation, we need a pointer (for example, the head in Zhao Majiang’s code) to record which element needs to be popped next; if the top of the stack is equal to b[head], we need to keep popping.
After completing the simulation, if the stack is indeed empty, it indicates that the output order is valid.
Since the number of elements ≤ 100000 is relatively small, we can define a temporary STL stack within the while loop for simulation, which eliminates the need to clear the stack after each set of data.
[Code Display]
#include<iostream>#include<stack>using namespace std;int a[100005],b[100005];int main(){ int q; cin>>q; for(int i=0;i<q;i++){ int n; cin>>n; for(int j=0;j<n;j++)cin>>a[j]; for(int j=0;j<n;j++)cin>>b[j]; stack<int> st; // Define a temporary stack int head=0; // Pointer for the element to be popped from b array for(int j=0;j<n;j++){ // Record how many elements have been popped st.push(a[j]); // After pushing an element, check if it needs to be popped while(st.top()==b[head]){ // If the top is equal, keep popping st.pop(); head++; if(st.empty())break;// If the stack is empty, exit the judgment and continue pushing } } if(st.empty()){ // If the stack is empty, the output order is valid cout<<"Yes"<<endl; } else cout<<"No"<<endl; } } return 0;}(Swipe left and right to view the complete code)
[Evaluation Results]
[Original Statement]
Creating original articles is not easy
Everyone is welcome to share in WeChat groups, Moments, and other social circles
If you need to reprint, please leave a message in the background to open the whitelist
Note: Unauthorized reproduction on other platforms is prohibited
If you think this is well written
Please help by liking, viewing, and following
Thank you!
Share
Collect
View
Like