数据结构算法题
数据结构算法题
通过键盘输入一个包括 '(' 和 ')' 的字符串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;
}
测试输出结果