1203：擴號匹配問題

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 7154 ??? 通過數: 3817

【題目描述】

在某個字符串（長度不超過100）中有左括號、右括號和大小寫字母；規定（與常見的算數式子一樣）任何一個左括號都從內到外與在它右邊且距離最近的右括號匹配。寫一個程序，找到無法匹配的左括號和右括號，輸出原來字符串，并在下一行標出不能匹配的括號。不能匹配的左括號用"$"標注,不能匹配的右括號用"?"標注。

【輸入】

輸入包括多組數據，每組數據一行，包含一個字符串，只包含左右括號和大小寫字母，字符串長度不超過100。

【輸出】

對每組輸出數據，輸出兩行，第一行包含原始輸入字符，第二行由"$","?"和空格組成，"$"和"?"表示與之對應的左括號和右括號不能匹配。

【輸入樣例】

((ABCD(x) )(rttyy())sss)(

【輸出樣例】

((ABCD(x) $$ )(rttyy())sss)( ? ?$

【分析】

? ? ? ? 這道題放到遞歸專題中，的確很難想，可以思考，掃描字符串，遇到左括號'('標記'$'，遇到右括號')'，則向前查找'$'，找到標記為空格，找不到標記問號'？'。

【參考代碼1】

#include <stdio.h> #include <string.h> #define N 110 char a[N],b[N]; int find_brace(int index) {if(index<0)return index;else if(b[index]=='$')return index;elsereturn find_brace(index-1); } int main() {int i,m,n;while(gets(a)!=NULL){n=strlen(a);memset(b,' ',sizeof(b));for(i=0;i<n;i++){if(a[i]=='(')b[i]='$';else if(a[i]==')'){m=find_brace(i-1);if(m==-1)b[i]='?';else{b[m]=' ';b[i]=' ';}}}puts(a);puts(b);memset(a,' ',sizeof(a));}return 0; }

? ? ? ? 事實上，可以用C++的STL模板中的stack（棧）實現。

【參考代碼2】

#include<iostream> #include <stack> const int N=110;using namespace std;string a; char b[N]; stack <int> s; int main() {while(getline(cin,a)){int len=a.size();for(int i=0;i<len;i++){if(a[i]=='('){s.push(i);b[i]=' ';}else if(a[i]==')'){if(!s.empty()){s.pop();b[i]=' ';}elseb[i]='?';}elseb[i]=' ';}while(!s.empty()) //棧不為空{b[s.top()]='$';s.pop();}b[len]='\0';cout<< a << endl;cout<< b << endl;}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1203

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1203：扩号匹配问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。