数据结构算法题

通过键盘输入一个包括 ‘(‘ 和 ‘)’ 的字符串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          : liaojx2016@126.com
*   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          : liaojx2016@126.com
*   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          : liaojx2016@126.com
*   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          : liaojx2016@126.com
*   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;
}

测试输出结果