首页 > 代码库 > 括号匹配问题，用栈实现

括号匹配问题，用栈实现

2024-07-03 05:58:45   222人阅读

用栈实现括号匹配其实是一个很简单的问题，思路在代码注释里面写的很清楚了，只是接口设置的好像不太好。

如果在main里面设置的str不是动态分布的，在linux下就会出错，不知道windows会不会出问题。

kuohao.cpp

#include <iostream>
#include "stack.cpp"
using namespace std;
//仅用于检测(),{},[],其他的符号原理都是一样的
bool isCase(const char c1,const char c2)//用于判断两个符号是否是匹配的
{
	char ch1=c1;
	char ch2=c2;
	if(ch1==‘(‘&&ch2==‘)‘)//for ()
		return true;
	if(ch1==‘[‘&&ch2==‘]‘)//for []
		return true;
	if(ch1==‘{‘&&ch2==‘}‘)//for {}
		return true;
	return false;//其他的都返回false

};
bool rightCase(const char c)//判断是否是右边的符号
{
	char ch=c;
	if(c==‘)‘||c==‘]‘||c==‘}‘)
		return true;
	return false;

};
bool  match(char *m)//m为待测字符串
{
	mStack<char> ma;
	char ch;
	char *p=m;
	char top;//=*p;//栈顶符号,top总是指向最急需匹配的项,即栈顶元素,先随便指定一个top，但不能是左边的符号
			//top并不就是栈顶，而是栈顶的一个副本
	while(*p!=‘\0‘)//字符串未结束
	{
		
		ch=*p;//获取p里面的元素
		if(rightCase(ch))//检测是否是右边元素,是则与top进行匹配检测，否则入栈，top换成ch
		{	
			if(ma.isEmpty())//如果栈为空，并且此时是右元素
				return false;
			if(isCase(top,ch))//否则进行匹配检查，若匹配，则top换成此时栈顶元素，
			{
				char temp;
				ma.Pop(temp);//temp其实就是之前的栈顶元素
				if(!ma.isEmpty())//如果取出一个元素之后，栈非空
				{
					ma.Pop(top);//令top复制现在的栈顶元素,因为此时栈顶被删除了，所以又要放回去
					ma.Push(top);//这样，top又和栈顶元素值一样了
				}//否则什么也不做，此时的top将会由下一个入栈的值重置
				
			}
			else	//倘若不匹配，则表明该序列不是匹配,因为最需匹配的项都无法匹配，不可能是匹配的
			 	return false;
		}	
		else	//不是右边符号，则入栈，并变更top
		{
			top=ch;//换top／／如果上一次出栈操作导致栈空了，top将在这里被重置
			ma.Push(ch);//ch入栈
		}
		p++;
		
	}
	if(ma.isEmpty())
		return true;
	return false;
};

main.cpp

#include "kuohao.cpp"
int main()
{
	//char *c[100];
	
	int i=5;
	while(i--)
	{
		char *str=new char[100];
		cout<<"please input the char **:";
		cin.getline(str,100);
		//cin.getline(c,100);
		cout<<str<<endl;
		//cout<<c<<endl;
		
		if(match(str))
			cout<<"this is match!"<<endl;
		else
			cout<<"doen‘t match!"<<endl;	
//		match(c);
		//cin.get();
		delete str;
	}
	
	
	return 0;
}




stack.cpp

//用于实现栈的操作
#include <iostream>
using namespace std;
//const int MAX=100；//栈最大长度值为100，用数组实现栈
//写成模板类是为了方便我以后使用
template <class T>
class mStack{
	private:
		enum {MAX=100};
		T arr[MAX];
		int Size;
		int top;//用于指示栈顶位置
	public:
		mStack(	)//构建空栈
		{
		  top=-1;//下标为-1则为空栈
		  Size=0;
		}
		bool isEmpty()
		{
			return top==-1;
		}
		bool isFull()
		{
			return top==MAX-1;
		}
		bool Push(T &item)
		{
			if(isFull())
			{
				cout<<"stack is full!"<<endl;
				return false;
			}
			//++top;
			//arr[++top]=item;
			arr[++top]=item;//因为下标从-1开始，使用前+1
			//cout<<"this "<<top<<" item push values is :"<<arr[top]<<endl;
			Size++;
			return true;
		}
		bool Pop(T &item)
		{
			if(isEmpty())
			{
				cout<<"stack is empty!"<<endl;
				return false;
			}
			item=arr[top--];//因为下标从-1开始，top指向当前最后一个元素,使用后-1
			//cout<<"this "<<top<<" item pop values is :"<<arr[top]<<endl;
			Size--;
			return true;
		}
		int size()
		{
			return Size;
		}

};



联系
我们