数据结构算法题

数据结构算法题

通过键盘输入一个包括  '(' 和 ')' 的字符串string ，判断字符串是否有效。要求设计算法实现检查字符串是否有效，有效的字符串需满足以下条件：
A.左括号必须用相同类型的右括号闭合。
B.左括号必须以精确的顺序闭合。
C.每个右括号都有一个对应的相同类型的左括号。
思路：

1.遍历字符串
2.创建链表
2。当遇到左括号存入链表，当遇到右括号左括号出栈
3.当出栈时检查到链表为空说明右括号多了，顺序不对，语法错误
4.当遍历完成之后，链表为空说明括号是配对的，字符串有效，否则说明左括号多了，字符串无效。
代码段
1.遍历字符串函数

1. /**********************************************************************************************
2. *   func name       : StrCheck
3. *   function        : Check whether string's bracket is right
4. *   func parameter  :
5. *                       @str :string to be checked
6. *                       @Head :address of head node
7. *   return resuolt  : Check result (true or false)
8. *   author          : liaojx2016@126.com
9. *   date            : 2024/04/25
10. *   note            : None
11. *   modify history  : None
12. *   function section: v1.0
13. *
14. **********************************************************************************************/
15. bool StrCheck(char *str,StackLList_t *head)
16. {
17.     bool flag=1;    //定义一个标志，用于返回检查结果
18.     //遍历字符，找出括号
19.     while (*str)
20.     {      
21.         //当字符为左括号，将其存入链表
22.         if (*str=='(')  {
23.             Stack_Push(*str,head);
24.         }
25.         //当字符为右括号，出栈
26.         if (*str==')')   {
27.             flag=Stack_Pop(head);
28.         }
29.         //当链表中没有结点，且字符为右括号，字符串语法错误，结束函数并返回0
30.         if (flag==0)    {
31.             return false;
32.         }
33.         str++;
34.     }
35.     //遍历完字符串之后，判断链表是否为空，若为空，表示语法正确，flag置1，若非空，则语法错误，flag置0。
36.     flag=Stack_IsEmpty(head);
37.     return flag;
38. }

复制代码

2.入栈函数

1. /**********************************************************************************************
2. *   func name       : StackLList_Push
3. *   function        : Do stack push for left bracket
4. *   func parameter  :
5. *                       @ch :Push charactor to stack
6. *                       @Head :Address of head node
7. *   return resuolt  : Stack push success result (true or false)
8. *   author          : liaojx2016@126.com
9. *   date            : 2024/04/25
10. *   note            : None
11. *   modify history  : None
12. *   function section: v1.0
13. *
14. **********************************************************************************************/
15. bool Stack_Push(char ch,StackLList_t *Head)
16. {
17.     //1.创建新的结点，并对新结点进行初始化
18.         StackLList_t *New = StackLList_NewNode(ch);
19.         if (NULL == New)
20.         {
21.                 printf("can not insert new node\n");
22.                 return false;
23.         }
24.         //2.判断链表是否为空，如果为空，则直接插入即可
25.         if (NULL == Head->next)
26.         {
27.                 Head->next = New;
28.                 return true;
29.         }
31.         //3.如果链表为非空，则把新结点插入到链表的头部
32.         New->next  = Head->next;
33.         Head->next = New;
34.         return true;
35. }

复制代码

3.出栈函数

1. /**********************************************************************************************
2. *   func name       : Stack_Pop
3. *   function        : Stack pop for one charactor
4. *   func parameter  :
5. *                       @Head :address of head node
6. *   return resuolt  : Stack pop success result (true or false)
7. *   author          : liaojx2016@126.com
8. *   date            : 2024/04/25
9. *   note            : None
10. *   modify history  : None
11. *   function section: v1.0
12. *
13. **********************************************************************************************/
14. bool Stack_Pop(StackLList_t *Head)
15. {
16.     //当链表为空，删除失败，返回false
17.     if (NULL == Head->next)
18.         {
19.                 //printf("Stack linklist is empty\n");
20.                 return false;
21.         }
22.     StackLList_t *Delnode=Head->next;   //备份首结点
23.     //printf("next=%#x\n",Head->next->next);
24.     //printf("the push element data is %d\n",Head->next->ch);
25.     //首部删除一个节点
26.     Head->next=Head->next->next;
27.     Delnode->next=NULL;
28.     free(Delnode);
29.     return true;
30. }

复制代码

4.判断链表为空

1. /**********************************************************************************************
2. *   func name       : Stack_IsEmpty
3. *   function        : Judge whether stack is empty
4. *   func parameter  :
5. *                       @Head :address of head node
6. *   return resuolt  : Check stack empty result (if empty,reture true.if not return false)
7. *   author          : liaojx2016@126.com
8. *   date            : 2024/04/25
9. *   note            : None
10. *   modify history  : None
11. *   function section: v1.0
12. *
13. **********************************************************************************************/
14. bool Stack_IsEmpty(StackLList_t *head)
15. {
16.     if (head->next==NULL)   
17.         return true;
18.     else
19.         return false;
20. }

复制代码

5.主函数

1. int main(int argc, char const *argv[])
2. {
3.     char *str="(j(k)ld)fd(((&)))))";
4.     //创建一个链表，存储左括号
5.     StackLList_t *head=StackLList_Create();
6.     printf("the words is %s\n",str);
7.     //判断字符串的括号是否符合语法
8.     //当检查函数返回1，则字符串语法正确，否则输出语法错误
9.     if (1==StrCheck(str,head))  {
10.         printf("the words is valid! \n");
11.     }
12.     else
13.         printf("the words is not valid!!!\n");
15.     return 0;
16. }

复制代码

测试输出结果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。