栈和队列的应用

发布于:2024-08-01 ⋅ 阅读:(74) ⋅ 点赞:(0)

栈在括号匹配中的应用

思路:

1.遍历字符数组

2.if为左括号,则入栈;

   if为右括号,

       1)空栈---返回false

        2)出栈e,if不匹配返回false,if匹配则继续循环

3.循环结束,判断栈是否为空.if为空栈,返回true,if非空,返回false

主要代码

1.判断左括号则入栈

if (str[i]=='['|| str[i] == '(' || str[i] == '{')
                  push(s, str[i]);

2.如果右括号先判断是否为空栈

if (stackEmpty(s))
              return false; 

3.判断右括号,出栈,判断是否为完整的括号

            char e;
            pop(s, e);
            if (e =='{'&& str[i]!='}')
            {return false;}
            if (e == '(' && str[i] != ')')
            { return false; }
            if (e == '[' && str[i] != ']')
            { return false; }

4.attention:计算字符数组长度

int length = (sizeof(str) / sizeof(str[0]))-1;

因为字符数组会默认在尾部加入'/0',所以计算得到的长度会比实际长度多1位.

5.代码

bool bracketCheck(char str[] ,int length) {
	//定义+初始化栈
	sqStack s;
	init(s);
	for (int i = 0; i < length; i++)
	{//判断为左括号还是右括号
		//左括号--入栈
		
		if (str[i]=='['|| str[i] == '(' || str[i] == '{')
		{
			push(s, str[i]);
		}
		else {
			//右括号--出栈
			//1.判断是否空栈--空false
		
			if (stackEmpty(s))
			{
				return false;
			}
			char e;
			//判断左括号右括号是否相符
			pop(s, e);
			if (e =='{'&& str[i]!='}')
			{
				return false;
			}
			if (e == '(' && str[i] != ')')
			{
				return false;
			}
			if (e == '[' && str[i] != ']')
			{
				return false;
			}
		}
	

	}
	return stackEmpty(s);
}

完整代码

#include<stdio.h>
#define MaxSize 10
//顺序栈定义
typedef struct sqStack {
	char data[MaxSize];
	int top;
}sqStack;
//初始化
void init(sqStack& s) {
	s.top = -1;
}
//进栈
bool push(sqStack &s,char e) {//e输入数据
	//判断是否栈满
	if (s.top==MaxSize-1)
	{
		return false;
	}
	s.data[++s.top] = e;
	return true;
}
//出栈
bool pop(sqStack& s, char &e) {
	//判断是否空栈
	if (s.top==-1)
	{
		return false;
	}
	e=s.data[s.top--];
	return true;
}
//判断空栈
bool stackEmpty(sqStack s) {
	if (s.top == -1)
	{
		return true;
	}
	return false;
}

//读取栈顶元素
bool getTop(sqStack &s,char &e) {
	//判断是否空栈
	if (s.top == -1)
	{
		return false;
	}
	e = s.data[s.top];
	return true;
}
bool bracketCheck(char str[] ,int length) {
	//定义+初始化栈
	sqStack s;
	init(s);
	for (int i = 0; i < length; i++)
	{//判断为左括号还是右括号
		//左括号--入栈
		
		if (str[i]=='['|| str[i] == '(' || str[i] == '{')
		{
			push(s, str[i]);
		}
		else {
			//右括号--出栈
			//1.判断是否空栈--空false
		
			if (stackEmpty(s))
			{
				return false;
			}
			char e;
			//判断左括号右括号是否相符
			pop(s, e);
			if (e =='{'&& str[i]!='}')
			{
				return false;
			}
			if (e == '(' && str[i] != ')')
			{
				return false;
			}
			if (e == '[' && str[i] != ']')
			{
				return false;
			}
		}
	

	}
	return stackEmpty(s);
}

int main() {
	char str[] = "{{[]([])}}";
	int length = (sizeof(str) / sizeof(str[0]))-1;//因为这里的长度还加入了'/0',所以会比书写的多一位
	if (bracketCheck(str, length)) {
		printf("配对成功!");
	}
	else {
		printf("sorry,配对失败!");
	}
}