資源簡介
某個序列完全由圓括號組成,一個“(”和“)”稱為一對括號,且序列中的括號成對出現。設n為序列中出現的括號對數,k為序列中括號的最大嵌套深度;那么,序列“((()()()))()(())”的n為8,k為3,請編程判斷任意給定的圓括號序列是否是一個深度為k的序列,如果是一個深度為k的序列,還要求輸出其括號的對數。
(1)先輸入嵌套深度k,然后輸入任意一個序列,最后給出判定結果(是,不是,或者輸入序列中的括號不配對)
(2)可以反復輸入數據,當k=0時,程序結束。當k≠0時輸入示例:
3
((()()()))()(())
2
(((()()()))())(())
5
(()()()))()((((()))))
輸出的判定結果:
測試1:是一個深度為3的括號序列,括號對數為8
測試2:不是一個深度為2的括號序列,是一個深度為4的括號序列,括號對數為9
測試3:括號不配對
代碼片段和文件信息
#include?
#include?
typedef?struct
{
????char?*S;
int?top;
int?base;
int?size;
}stack;
stack?*OPTR;
int?pro_depth;//獲取用戶輸入的序列深度
void?InitStack(stack?*st)
{
????st->S?=?(char*)malloc(20*sizeof(char));
if(!st->S)?exit(1);
st->top?=?st->base?=?0;
st->size?=?20;
}
/*操作結果:構造一個空棧st*/
void?Push(stack?*stchar?c)
{
????if(st->top?-?st->base?>=?st->size)
{
????st->S?=?(char*)realloc(st->S(st->size?+?10)?*?sizeof(char));
if(!st->S)?exit(1);
st->size?+=?10;
}
st->S[st->top]?=?c;
st->top++;
}
/*初始條件:棧st已存在
??操作結果:插入元素c為新的桟頂元素
*/
char?Gettop(stack?*st)
{
char?e;
if(st->top?==?0?&&?st->base?==?0)
{
exit(1);
}
e?=?st->S[st->top-1];
return?e;
}
/*初始條件:棧st已存在且非空
??操作結果:用e返回st的桟頂元素
*/
void?Pop(stack?*st)
{
if(st->top?==?st->base)
exit(1);
else
{
st->top--;
}
}
/*初始條件:棧st已存在且非空
??操作結果:刪除st的桟頂元素
*/
void?JudgementResult(stack?*stint?a?int?b)
{
if(st->S[st->top-1]?==?‘#‘)//若棧st中只有‘#’,則證明匹配成功,否則失敗
{
if((b-1)?==?pro_depth)//若根據序列所求得的深度與用戶給定深度相等,則輸出是該深度的序列,否則不是
{
????printf(“您輸入的序列是一個深度為%d的圓括號序列,括號對數為%d\n“b-1a);
getchar();
}
else
{
printf(“您輸入的序列不是一個深度為%d的圓括號序列,是一個深度為%d的序列,括號對數為%d\n“pro_depthb-1a);
getchar();
}
}
else
{
printf(“您輸入的序列不是匹配的圓括號序列!“);
getchar();
}
pro_depth?=?0;
}
/*
??操作結果:判斷括號序列是否匹配
*/
void?ParenthesisMatch()
{
char?c;//獲取用戶輸入的序列字符
char?a;//獲取棧st頂字符
int?count1?=?0;//定義棧st當前深度,并取最大值作為序列深度
????int?count2?=?0;//定義括號對數
????int?depth?=?0;//定義序列深度,該深度為count2的最大值
InitStack(OPTR);
Push(OPTR‘#‘);//現將一個‘#‘壓入棧st中,用以最后判定圓括號是否全部出棧
printf(“請輸入一個完全由圓括號組成的序列以‘#’表示結束:\n“);
c?=?getchar();
while(c?!=?‘#‘)//判斷是否讀取到括號序列的最后一個字符,讀到‘#’時,結束循環
{
if(c?!=?‘)‘?&&?c?!=?‘(‘)//排除其他字符的干擾
{
printf(“請輸入正確的格式!\n“);
exit(0);
}
else
{
????a?=?Gettop(OPTR);//讀取棧st頂元素
????if(c?==?‘(‘?||?a?==?‘#‘)//若桟頂元素為‘(’或‘#’,直接壓入棧S中,記錄
- 上一篇:音標mp3
- 下一篇:UMI復制工具內含狗數據
評論
共有 條評論