生活随笔
收集整理的這篇文章主要介紹了
(栈)括号匹配
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目
一個串，只包含(和)。一個(能唯一匹配一個)，但是(必須出現在)之前，請判斷括號能否完全匹配，如果能，輸出配對的括號位置，匹配括號只能嵌套不能交叉。
輸入：一個只由(和)構成的字符串，長度<50000。
輸出：不匹配輸出no，否則，輸出yes，接下來若干行，每行輸出2整數，空格隔開，表示匹配括號位置，下標從一開始，可以任意順序輸出。
分析與解答：
這個就是遇到左括號把下標壓入棧，遇到右括號棧頂出棧，并且做標記，ans[i]=a.top()，意味著有括號的位置在i，左括號的位置在k。
如果循環時候遇見右括號，但是此時棧為空，說明左括號少了，如果循環完不為空，說明左括號多了。
最后遍歷一遍標記數組，輸出值和下標即可
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std
;
char s
[50010];
int ans
[50010];
int main(){scanf("%s",s
);stack
<int> a
;int n
=strlen(s
),f
=1;for(int i
=0;i
<n
;++i
){if(s
[i
]=='('){a
.push(i
+1);}else{if(!a
.empty()){ans
[i
+1]=a
.top();a
.pop();}else {f
=0;break;}}}if(!a
.empty()||!f
){cout
<<"No";}else{cout
<<"Yes"<<endl
;for(int i
=0;i
<=n
;++i
){if(ans
[i
]) cout
<<ans
[i
]<<' '<<i
<<endl
;}}return 0;
}
總結
以上是生活随笔為你收集整理的(栈)括号匹配的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
