假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判别，表达式中的括号是否配对，以字符“\0“作为算术表达式的结束符
思想:这道题是栈的应用类型，我们可以建立一个栈来保存'(','[','{',通过遍历字符串如果是三个左括号其中一个则入栈，当遇到')'']''}'则出栈配对，如果左右匹配，则遍历下一个元素，如果不匹配直接返回，如果遍历字符串结束，但栈中还有元素，则是左符号单身，如果已经空栈，但是又遍历到一个右括号，则是右括号单身
具体代码:
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LinkStack
{
char data;
struct LinkStack* next;
}LinkStack;
void InitStack(LinkStack** S)//初始化栈(不带头结点链表实现)
{
(*S) = NULL;
return;
}
bool Push(LinkStack** S,char ch)//入栈
{
if (ch == '(' || ch == '[' || ch == '{')
{
LinkStack* p = (LinkStack*)malloc(sizeof(LinkStack));
if (p == NULL)
return false;
//第一次入栈
if ((*S) == NULL)
{
p->data = ch;
p->next = NULL;
(*S) = p;
}
//后续入栈
else
{
p->data = ch;
p->next = (*S);
(*S) = p;
}
}
return true;
}
bool Pop(LinkStack** S)//出栈并且带回元素
{
if ((*S) == NULL)//空栈无法出栈
return false;
LinkStack* p = (*S);
//*x = p->data;
(*S) = p->next;
free(p);
return true;
}
LinkStack* GetTop(LinkStack* S)//返回栈顶指针
{
if (S == NULL)//空栈
return NULL;
LinkStack* p = S;
return p;
}
bool EmptyStack(LinkStack* S)//判断空栈
{
if (S == NULL)
return true;
return false;
}
void JudgeStack(LinkStack **S,char arr[])//判断
{
char* a = arr;
while (*a != '\0')
{
if (*a == '(' || *a == '[' || *a == '{')//如果当时是三个括号其中一个则入栈
Push(S, *a);
else if (EmptyStack(*S) == false && *a == ')' && GetTop((*S))->data == '(')//如果是'('则出栈
Pop(S);
else if (EmptyStack(*S) == false && *a == ')' && GetTop((*S))->data != '(')//如果不是则直接退出
{
printf("配对失败\n");
printf("%c %c\n",*a, GetTop((*S))->data);
return;
}
else if (EmptyStack(*S) == false && *a == ']' && GetTop((*S))->data == '[')//如果是'['则出栈
Pop(S);
else if (EmptyStack(*S) == false && *a == ']' && GetTop((*S))->data != '[')
{
printf("配对失败\n");
printf("%c %c\n", *a, GetTop((*S))->data);
return;
}
else if (EmptyStack(*S) == false && *a == '}' && GetTop((*S))->data == '{')//如果是'{'则出栈
Pop(S);
else if (EmptyStack(*S) == false && *a == '}' && GetTop((*S))->data != '{')
{
printf("配对失败\n");
printf("%c %c\n", *a, GetTop((*S))->data);
return;
}
else if (EmptyStack(*S) == true && (*a == ')' || *a == ']' || *a == '}'))//如果栈为空，且字符串中还有元素
printf("右括号单身\n");
a++;//向后遍历字符串
}
if (EmptyStack(*S) == false)//如果字符串已遍历结束但栈里还有元素
printf("左括号单身\n");
else
printf("配对成功\n");
return;
}
int main()
{
char arr[] = "[(3 + 2) * 5 + 3](]()";
LinkStack* S;//指向栈的指针
InitStack(&S);//初始化栈
JudgeStack(&S , arr);
return 0;
}
注:此代码中运用了大量的if-else语句，不是很美观(其实懒得改了)，大家如果要引用可以自行优化代码