數據結構演算法題

通過鍵盤輸入一個包括 '(' 和 ')' 的字元串string ，判斷字元串是否有效。要求設計演算法實現檢查字元串是否有效，有效的字元串需滿足以下條件：

A.左括弧必須用相同類型的右括弧閉合。
B.左括弧必須以正確的順序閉合。
C.每個右括弧都有一個對應的相同類型的左括弧。

思路：

1.遍歷字元串

2.創建鏈表

2。當遇到左括弧存入鏈表，當遇到右括弧左括弧出棧

3.當出棧時檢查到鏈表為空說明右括弧多了，順序不對，語法錯誤

4.當遍歷完成之後，鏈表為空說明括弧是配對的，字元串有效，否則說明左括弧多了，字元串無效。

代碼段

1.遍歷字元串函數

/**********************************************************************************************
*   func name       : StrCheck
*   function        : Check whether string's bracket is right
*   func parameter  : 
*                       @str :string to be checked
*                       @Head :address of head node 
*   return resuolt  : Check result (true or false)
*   author          : [email protected]
*   date            : 2024/04/25
*   note            : None
*   modify history  : None
*   function section: v1.0
*
**********************************************************************************************/
bool StrCheck(char *str,StackLList_t *head)
{
    bool flag=1;    //定義一個標誌，用於返回檢查結果
    //遍歷字元，找出括弧
    while (*str)
    {       
        //當字元為左括弧，將其存入鏈表
        if (*str=='(')  {
            Stack_Push(*str,head);
        }
        //當字元為右括弧，出棧
        if (*str==')')   {
            flag=Stack_Pop(head);
        }
        //當鏈表中沒有結點，且字元為右括弧，字元串語法錯誤，結束函數並返回0
        if (flag==0)    {
            return false;
        }
        str++;
    }
    //遍歷完字元串之後，判斷鏈表是否為空，若為空，表示語法正確，flag置1，若非空，則語法錯誤，flag置0。
    flag=Stack_IsEmpty(head);
    return flag; 
}

2.入棧函數

/**********************************************************************************************
*   func name       : StackLList_Push
*   function        : Do stack push for left bracket
*   func parameter  : 
*                       @ch :Push charactor to stack
*                       @Head :Address of head node
*   return resuolt  : Stack push success result (true or false)
*   author          : [email protected]
*   date            : 2024/04/25
*   note            : None
*   modify history  : None
*   function section: v1.0
*
**********************************************************************************************/
bool Stack_Push(char ch,StackLList_t *Head)
{
    //1.創建新的結點，並對新結點進行初始化
	StackLList_t *New = StackLList_NewNode(ch);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	//2.判斷鏈表是否為空，如果為空，則直接插入即可
	if (NULL == Head->next)
	{
		Head->next = New;
		return true;
	}

	//3.如果鏈表為非空，則把新結點插入到鏈表的頭部
	New->next  = Head->next;
	Head->next = New;
	return true;
}

3.出棧函數

/**********************************************************************************************
*   func name       : Stack_Pop
*   function        : Stack pop for one charactor
*   func parameter  : 
*                       @Head :address of head node 
*   return resuolt  : Stack pop success result (true or false)
*   author          : [email protected]
*   date            : 2024/04/25
*   note            : None
*   modify history  : None
*   function section: v1.0
*
**********************************************************************************************/
bool Stack_Pop(StackLList_t *Head)
{
    //當鏈表為空，刪除失敗，返回false
    if (NULL == Head->next)
	{
		//printf("Stack linklist is empty\n");
		return false;
	}
    StackLList_t *Delnode=Head->next;   //備份首結點
    //printf("next=%#x\n",Head->next->next);
    //printf("the push element data is %d\n",Head->next->ch);
    //首部刪除一個節點
    Head->next=Head->next->next;
    Delnode->next=NULL;
    free(Delnode);
    return true;
}

4.判斷鏈表為空

/**********************************************************************************************
*   func name       : Stack_IsEmpty
*   function        : Judge whether stack is empty
*   func parameter  : 
*                       @Head :address of head node 
*   return resuolt  : Check stack empty result (if empty,reture true.if not return false)
*   author          : [email protected]
*   date            : 2024/04/25
*   note            : None
*   modify history  : None
*   function section: v1.0
*
**********************************************************************************************/
bool Stack_IsEmpty(StackLList_t *head)
{
    if (head->next==NULL)   
        return true;
    else 
        return false;
}

5.主函數

int main(int argc, char const *argv[])
{
    char *str="(j(k)ld)fd(((&)))))";
    //創建一個鏈表，存儲左括弧
    StackLList_t *head=StackLList_Create();
    printf("the words is %s\n",str);
    //判斷字元串的括弧是否符合語法
    //當檢查函數返回1，則字元串語法正確，否則輸出語法錯誤
    if (1==StrCheck(str,head))  {
        printf("the words is valid! \n");
    }
    else
        printf("the words is not valid!!!\n");

    return 0;
}

測試輸出結果