欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-25 08:33:05
...

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

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

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

1. 项目结构

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

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. 测试结果

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