總時間限制:?1000ms ?內存限制:?65536kB描述

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

輸入

輸入包括多組數據，每組數據一行，包含一個字符串，只包含左右括號和大小寫字母，字符串長度不超過100
注意：cin.getline(str,100)最多只能輸入99個字符！

輸出

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

樣例輸入

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

樣例輸出

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

題目鏈接：http://ica.openjudge.cn/function2/5/

分析：主要是用到棧，這里用數組直接模擬即可。棧里面保存字符串中左括號的下標。掃描字符串，遇到左括號則下標入棧，遇到右括號則檢驗棧是否為空，不為空則出棧并將對用的左右括號字符位置標記空格，否則將右括號字符對應位置標記“?”。

掃描完成以后，再掃描棧，把多余的左括號字符對應位置標記“$”.

代碼：

1 #include<stdio.h> 2 #include<string.h> 3 int main(int argc, char *argv[]) 4 { 5 char str[110]; 6 int len,i,k; 7 int stack[110],end=0; 8 while(scanf("%s",str)!=EOF) 9 { 10 printf("%s\n",str); 11 end=0; 12 len=strlen(str); 13 for(i=0;i<len;i++) 14 { 15 if(str[i]!='('&&str[i]!=')') str[i]=' '; 16 } 17 for(i=0;i<len;i++) 18 { 19 if(str[i]=='(') 20 { 21 stack[end]=i; 22 end++; 23 } 24 else if(str[i]==')') 25 { 26 if(end>0)//棧不為空，則 27 { 28 k=stack[end-1]; 29 str[k]=' ';//棧頂的左括號和新遇到的右括號匹配 30 str[i]=' '; 31 end--;//棧頂元素出棧 32 } 33 else 34 { 35 str[i]='?';//右括號不匹配 36 } 37 } 38 } 39 while(end>0) 40 { 41 k=stack[end-1]; 42 str[k]='$'; 43 end--; 44 } 45 printf("%s\n",str); 46 } 47 return 0; 48 }

遞歸的代碼：

遞歸的思路可以參考“排隊游戲”這一題的遞歸代碼：http://www.cnblogs.com/huashanqingzhu/p/7238768.html

1 #include<stdio.h> 2 #include<string.h> 3 int fun(char *str,int len,int nowIndex);//nowIndex表示當前掃描到的字符下標。返回右括號的下標或-1 4 int count=0;//表示當前已經遞歸保存的左括號的個數 5 int main(int argc, char *argv[]) 6 { 7 char str[110]; 8 int len,i,k; 9 while(scanf("%s",str)!=EOF) 10 { 11 printf("%s\n",str); 12 len=strlen(str); 13 for(i=0;i<len;i++) 14 { 15 if(str[i]!='('&&str[i]!=')') str[i]=' '; 16 } 17 count=0; 18 fun(str,len,0); 19 printf("%s\n",str); 20 } 21 return 0; 22 } 23 int fun(char *str,int len,int nowIndex)//nowIndex表示當前掃描到的字符下標。返回右括號的下標或-1 24 { 25 int temp; 26 if(nowIndex<len) 27 { 28 if(str[nowIndex]==')') 29 { 30 if(count>0) 31 return nowIndex; 32 else 33 { 34 str[nowIndex]='?'; 35 return fun(str,len,nowIndex+1); 36 } 37 } 38 else if(str[nowIndex]==' ') 39 return fun(str,len,nowIndex+1); 40 else 41 { 42 count++; 43 temp=fun(str,len,nowIndex+1);//獲取當前左括號對應的右括號 44 if(temp!=-1) 45 { 46 str[temp]=' '; 47 str[nowIndex]=' '; 48 count--; 49 return fun(str,len,temp+1); 50 } 51 else 52 { 53 str[nowIndex]='$';//temp==-1表示當前的左括號是多余的，不可匹配的 54 return -1; 55 } 56 } 57 } 58 return -1; 59 }

?

轉載于:https://www.cnblogs.com/huashanqingzhu/p/7239039.html

總結

以上是生活随笔為你收集整理的扩号匹配问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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