題目：
? 輸入一個(gè)包括 '(' 和 ')' 的字符串string ，判斷字符串是否有效。要求設(shè)計(jì)算法實(shí)現(xiàn)檢查字符串是否有效，有效的字符串需滿足以下條件：
A. 左括號(hào)必須用相同類型的右括號(hào)閉合。
B. 左括號(hào)必須以正確的順序閉合。
C. 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。
題目分析：
? 該題需要滿足三個(gè)條件，左括號(hào)類型，數(shù)量，順序都得一致，所以選擇使用順序棧結(jié)構(gòu)來實(shí)現(xiàn)。
? 主要思路為遍歷兩次字符串。第一次遍歷時(shí)，將遇到的左括號(hào)依次存入順序棧中；第二次遍歷時(shí)，每當(dāng)遇到右括號(hào)時(shí)，便執(zhí)行彈棧操作，并將彈棧出的元素與右括號(hào)類型進(jìn)行對(duì)比。若類型一致，則繼續(xù)遍歷；若類型不一致，則將此時(shí)的棧頂元素下標(biāo)加一且終止遍歷，代表該字符串無效。
? 最后通過判斷順序棧中棧頂元素下標(biāo)是否為-1，即順序棧中是否還有元素，來判定字符串是否有效。
原理圖示：
代碼實(shí)現(xiàn)：
/*********************************************************************
*
* name : SeqStack_JudgString
* function : 根據(jù)用戶輸入的字符串中的括號(hào)個(gè)數(shù)與匹配度進(jìn)行判斷字符串的
正確性
* argument :
* @Manager :順序棧的地址
*
* retval : 調(diào)用成功返回新的棧地址
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
void SeqStack_JudgString( DataType_t *str)
{
//創(chuàng)建順序棧
SeqStack_t *SequenceStack = SeqStack_Create(sizeof(str));
//計(jì)算得到的字符串長(zhǎng)度
int n = strlen(str);
//遍歷得到的字符串,將字符串中各中類型的左括號(hào)按先后順序放入順序棧中
for (int i = 0; i < n;i++)
{
if(str[i] == '(')
SeqStack_Push(SequenceStack, str[i]);
else if(str[i] == '[')
SeqStack_Push(SequenceStack, str[i]);
else if(str[i] == '{')
SeqStack_Push(SequenceStack, str[i]);
}
//再次對(duì)字符串遍歷，找到對(duì)應(yīng)的右括號(hào)，并且判斷類型是否相符合
for (int i = 0; i < n; i++)
{
if(str[i] == ')')
{
DataType_t temp = SeqStack_Pop(SequenceStack);
if('('== temp) //彈棧出的元素是相同類型的左括號(hào)時(shí)，繼續(xù)遍歷
continue;
else
{
SequenceStack->Top++;
break;
}
}
else if(str[i] == ']')
{
DataType_t temp1 = SeqStack_Pop(SequenceStack);
if('[' == temp1)
continue;
else
{
SequenceStack->Top++;
break;
}
}
else if(str[i] == '}')
{
DataType_t temp2 = SeqStack_Pop(SequenceStack);
if('{'== temp2)
continue;
else
{
SequenceStack->Top++;
break;
}
}
}
//判斷匹配后的左右括號(hào)數(shù)量是否一致
if(SequenceStack->Top == -1)
printf("The string is valid!\n");
else
printf("The string is invalid!\n");
return;
}
代碼整體展示：
/*******************************************************************
*
* file name: SequenceStack_demo.c
* author : 790557054@qq.com
* date : 2024/04/25
* function : 該案例是利用順序棧實(shí)現(xiàn)判斷一個(gè)字符串是否有效，即通過判斷
括號(hào)數(shù)是否能夠正確匹配得出結(jié)論
* note : None
*
* CopyRight (c) 2023-2024 790557054@qq.com All Right Reseverd
*
* *****************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
//指的是順序棧中的元素的數(shù)據(jù)類型，用戶可以根據(jù)需要進(jìn)行修改
typedef char DataType_t;
//構(gòu)造記錄順序棧SequenceStack各項(xiàng)參數(shù)(棧底地址+棧容量+棧頂元素的下標(biāo))的結(jié)構(gòu)體
typedef struct SequenceStack
{
DataType_t * Bottom; //記錄棧底地址
unsigned int Size; //記錄棧容量
int Top; //記錄棧頂元素的下標(biāo)
}SeqStack_t;
/*********************************************************************
*
* name : SeqStack_Create
* function : 創(chuàng)建一個(gè)空的順序棧，并為記錄順序棧信息的結(jié)構(gòu)體
申請(qǐng)堆內(nèi)存，并進(jìn)行初始化即可！
* argument :
* @size :棧的容量大小
*
* retval : 調(diào)用成功返回順序棧的地址
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
//創(chuàng)建順序表并對(duì)順序棧進(jìn)行初始化
SeqStack_t * SeqStack_Create(unsigned int size)
{
//1.利用calloc為順序棧的管理結(jié)構(gòu)體申請(qǐng)一塊堆內(nèi)存
SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));
if(NULL == Manager)
{
perror("calloc memory for manager is failed");
exit(-1); //程序異常終止
}
//2.利用calloc為所有元素申請(qǐng)堆內(nèi)存
Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));
if (NULL == Manager->Bottom)
{
perror("calloc memory for Stack is failed");
free(Manager);
exit(-1); //程序異常終止
}
//3.對(duì)管理順序棧的結(jié)構(gòu)體進(jìn)行初始化（元素容量 + 最后元素下標(biāo)）
Manager->Size = size; //對(duì)順序棧中的容量進(jìn)行初始化
Manager->Top = -1; //由于順序棧為空，則棧頂元素的下標(biāo)初值為-1
return Manager;
}
/*********************************************************************
*
* name : SeqStack_IsFull
* function : 判斷順序棧是否已滿
* argument :
* @Manager :順序棧的地址
*
* retval : 調(diào)用成功返回bool型，滿了則返回true，沒滿返回false
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
bool SeqStack_IsFull(SeqStack_t *Manager)
{
return (Manager->Top + 1 == Manager->Size) ? true : false;
}
/*********************************************************************
*
* name : SeqStack_Push
* function : 根據(jù)棧的特性，把新元素從棧頂入棧，也就是從數(shù)組的尾部進(jìn)行元素插入
* argument :
* @Manager :順序棧的地址
@Date :要入棧的數(shù)據(jù)
*
* retval : 調(diào)用成功返回bool型，滿了則返回true，沒滿返回false
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
//入棧
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
//1.判斷順序棧是否已滿
if ( SeqStack_IsFull(Manager) )
{
printf("SeqStack Full is Full!\n");
return false;
}
//2.如果順序棧有空閑空間，則把新元素添加到順序棧的棧頂
Manager->Bottom[++Manager->Top] = Data;
return true;
}
/*********************************************************************
*
* name : SeqStack_IsEmpty
* function : 判斷順序棧是否為空
* argument :
* @Manager :順序棧的地址
*
* retval : 調(diào)用成功返回bool型，空了則返回true，沒空返回false
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
return (-1 == Manager->Top) ? true : false;
}
/*********************************************************************
*
* name : SeqStack_Pop
* function : 根據(jù)棧的特性，把元素從棧頂出棧，也就是把元素從數(shù)組的尾部把元素刪除
* argument :
* @Manager :順序棧的地址
*
* retval : 調(diào)用成功返回新的棧地址
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
//出棧
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
DataType_t temp = 0; //用于存儲(chǔ)出棧元素的值
//1.判斷順序棧是否為空
if ( SeqStack_IsEmpty(Manager) )
{
// printf("SeqStack is Empty!\n");
return -1;
}
//2.由于刪除了一個(gè)元素，則需要讓順序棧的棧頂元素下標(biāo)-1
temp = Manager->Bottom[Manager->Top--];
return temp;
}
/*********************************************************************
*
* name : SeqStack_JudgString
* function : 根據(jù)用戶輸入的字符串中的括號(hào)個(gè)數(shù)與匹配度進(jìn)行判斷字符串的
正確性
* argument :
* @Manager :順序棧的地址
*
* retval : 調(diào)用成功返回新的棧地址
* author : 790557054@qq.com
* date : 2024/04/25
* note : none
*
* *****************************************************************/
void SeqStack_JudgString( DataType_t *str)
{
//創(chuàng)建順序棧
SeqStack_t *SequenceStack = SeqStack_Create(sizeof(str));
//計(jì)算得到的字符串長(zhǎng)度
int n = strlen(str);
//遍歷得到的字符串,將字符串中各中類型的左括號(hào)按先后順序放入順序棧中
for (int i = 0; i < n;i++)
{
if(str[i] == '(')
SeqStack_Push(SequenceStack, str[i]);
else if(str[i] == '[')
SeqStack_Push(SequenceStack, str[i]);
else if(str[i] == '{')
SeqStack_Push(SequenceStack, str[i]);
}
//再次對(duì)字符串遍歷，找到對(duì)應(yīng)的右括號(hào)，并且判斷類型是否相符合
for (int i = 0; i < n; i++)
{
if(str[i] == ')')
{
DataType_t temp = SeqStack_Pop(SequenceStack);
if('('== temp) //彈棧出的元素是相同類型的左括號(hào)時(shí)，繼續(xù)遍歷
continue;
else
{
SequenceStack->Top++;
break;
}
}
else if(str[i] == ']')
{
DataType_t temp1 = SeqStack_Pop(SequenceStack);
if('[' == temp1)
continue;
else
{
SequenceStack->Top++;
break;
}
}
else if(str[i] == '}')
{
DataType_t temp2 = SeqStack_Pop(SequenceStack);
if('{'== temp2)
continue;
else
{
SequenceStack->Top++;
break;
}
}
}
//判斷匹配后的左右括號(hào)數(shù)量是否一致
if(SequenceStack->Top == -1)
printf("The string is valid!\n");
else
printf("The string is invalid!\n");
return;
}
int main(int argc, char const *argv[])
{
while(1)
{
//定義一個(gè)字符串指針變量 用于存儲(chǔ)用戶輸入的字符串
DataType_t str[200];
printf("Please input a string containing parentheses :\n ");
scanf("%s", str);
SeqStack_JudgString( str);
}
return 0;
}
結(jié)果驗(yàn)證:
待優(yōu)化問題：
- 如果右括號(hào)在最前面時(shí)，應(yīng)該判斷是無效，但是目前算法無法判斷，例如：）（1+2 該算法會(huì)判斷有效 是錯(cuò)誤判斷
優(yōu)化思路：
? 將判斷’（‘和 ’）‘的判斷放進(jìn)一個(gè)循環(huán)里面判斷，這樣比兩次遍歷的時(shí)間復(fù)雜度更低，需要吸取教訓(xùn)，優(yōu)化自身解題思路，思考更多樣的情況。
圖示：文章來源：http://www.zghlxwxcb.cn/news/detail-858648.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-858648.html
到了這里，關(guān)于練習(xí)題----順序棧算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
