数据结构中括号匹配的代码实现(C语言)

声明：括号匹配的实现使用的是.cpp文件。

• 由于我使用的是vs2010，vs2010的编译器不支持函数返回值bool类型，并且不能这样定义for(int i= 0; i < 10; i++)，必须在函数的开头声明i=0。为了编写的方便，我使用的是.cpp文件，没有使用.c文件。虽然是c++文件，但是内容是c语言。如果有需要.c文件的，请自行修改这两个地方就可以了。

注意：项目中使用的栈是动态链式栈(带头结点)。

1. 项目结构

2. LinkStack.h

/*
* 使用动态链表实现链式栈(不带头结点)
*/


// 1. 定义抽象数据类型
typedef struct {
	char elem;
} ElemType;

// 2. 定义链式栈的结点
typedef struct LNode{
	ElemType data;
	struct LNode * next;
} LNode;

// 3. 定义一些接口

/**
* func:初始化链式栈
* @head：头指针
*/
void initStack(LNode ** head);


/**
* func:销毁链式栈
* @head：头指针
*/
bool isStackEmpty(LNode * head);


/**
* func:判断栈是否为空
* @head：头指针
*/
void destroyStack(LNode ** head);


/**
* func:向栈顶压入元素
* @head：头指针
* @x：要添加的元素
*/
bool push(LNode * head, ElemType x);


/**
* func:弹出栈顶元素
* @head：头指针
* @x：存放要删除的元素
*/
bool pop(LNode * head, ElemType * x);


/**
* func:查看栈顶元素
* @head：头指针
* @x：存放要查看的元素
*/
bool selectStackTopElem(LNode * head, ElemType * x);

3. LinkStack.cpp

#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"

/**
* func:初始化链式栈
*/
void initStack(LNode ** head) {
	*head = (LNode *)malloc(sizeof(LNode));
	(*head)->next = NULL;
}


/**
* func判断栈是否为空
* @head：头指针
*/
bool isStackEmpty(LNode * head) {
	if (head->next == NULL)
		return true;
	else
		return false;
}


/**
* func:销毁链式栈
* @head：头指针
*/
void destroyStack(LNode ** head) {
	LNode * t;
	while(*head != NULL) {
		t = *head;
		*head = (*head)->next;
		free(t);
	}
	*head = t = NULL;
}


/**
* func:向栈顶压入元素
* @head：头指针
* @x：要添加的元素
*/
bool push(LNode * head, ElemType x) {
	// 先动态分配一个结点
	if (head == NULL)
		return false;
	LNode * temp = (LNode *)malloc(sizeof(LNode));
	if (temp == NULL)
		return NULL;
	// 再将该结点压入栈中
	temp->data = x;
	temp->next = head->next;
	head->next = temp;
	return true;
}


/**
* func:弹出栈顶元素
* @head：头指针
* @x：存放要删除的元素
*/
bool pop(LNode * head, ElemType * x) {
	// 判断栈是否为空
	if (isStackEmpty(head)) 
		return false;
	// 栈不为空，则删除栈顶元素
	LNode * p = head->next;
	*x = p->data;
	head->next = p->next;
	free(p);
	p = NULL;
	return true;
}


/**
* func:查看栈顶元素
* @head：头指针
* @x：存放要查看的元素
*/
bool selectStackTopElem(LNode * head, ElemType * x) {
	// 判断栈是否为空
	if (isStackEmpty(head)) 
		return false;
	// 栈不为空，则查看栈顶元素
	*x = head->next->data;
	return true;
}

4. main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"


/**
* func:将字符封装为抽象数据类型，方便使用之前写过的链式栈
* @x：要封装的字符
* return:封装的抽象数据类型
*/
ElemType getElem(char x) {
	ElemType temp;
	temp.elem = x;
	return temp;
}

/**
* func:对一个字符串进行括号匹配，如果是对的就返回true，错的就返回false
* @str：要检测的字符串
* @length：字符串str的长度
* return:括号匹配是对的，则返回true，错的就返回false
*/
bool bracketCheck(char * str, int length) {
	// 初始化一个栈
	LNode * stack;
	initStack(&stack);
	// 遍历字符串
	for (int i = 0; i < length; i++) {
		// 判断当前元素是否为左括号
		if (str[i] == '(' || str[i] == '{' || str[i] == '[') //如果是左括号，则压入栈中
			push(stack, getElem(str[i]));
		else {	// 右括号则与栈弹出的元素比较
			// 判断栈是否为空
			if (isStackEmpty(stack))
				return false; // 若栈为空，说明不匹配
			// 弹出栈顶元素，判断是否与该元素相等
			ElemType temp;
			pop(stack, &temp);
			if (str[i] == ')' && temp.elem != '(')
				return false;
			if (str[i] == '}' && temp.elem != '{')
				return false;
			if (str[i] == ']' && temp.elem != '[')
				return false;
		}
	}
	return isStackEmpty(stack);
}


void main() {
	char a[50];
	printf("请输入一个括号字符串:");
	scanf("%s", a);
	// 判断该括号字符串是否合法
	if (bracketCheck(a, strlen(a)))
		printf("判断结果：合法\n");
	else
		printf("判断结果：不合法\n");
}

5. 测试结果