如何用栈实现简单的括号匹配

思路很简单，利用栈的压栈出栈的特点，输入的字符为“（”就入栈，“）”就出栈，如果栈是空，就是匹配成功，因为“（）”成对出现。

接下来为代码实现，分别是C++本身的STL库中的stack和自己手写的stack功能实现： C++STL:

#include<iostream>

#include<stack>

using namespace std;
stack<int>st;
int main(){
	char x;
	int flag,a,b;
	while(cin>>x){
		if(x=='('){
			st.push(x);
		}
		if(x==')'){
			st.pop();
		}
		if(st.empty()){
			flag=1;
		}
		else {
			flag=0;
		}
	}
	if(flag){
		cout<<"1"<<endl;
	}else {
		cout<<"0"<<endl;
	}
	return 0;
}

自己手写的栈功能：

#include<iostream>

using namespace std;
const int  maxsize=100;
typedef char datatype;
typedef char ElemType;
typedef struct{
	datatype data[maxsize];
	int top;
}sqstack; 

void init_sqstack(sqstack *sq){
	sq->top=-1;
}

int empty(sqstack *sq){
	if(sq->top==-1){
		return 1;
	}
	else return 0;
}

int push_sqstack(sqstack *sq,datatype x){
		if(sq->top==maxsize-1){
		cout<<"栈满，不能进栈!\n";
		return 0;
	}
	sq->data[++sq->top]=x;
	return 1;
}

int pop_sqstack(sqstack *sq,datatype *x){
	if(sq->top==-1){
		cout<<"栈空，不能退栈!\n";
		return 0;
	}
	*x=sq->data[sq->top--];
	return 1;
}

int gettop_sqstack(sqstack *sq,datatype *x){
	if(sq->top==-1){
		cout<<"栈空，无栈顶可取!\n";
		return 0;
	}
	*x=sq->data[sq->top];
	return 1;
}

int result(){
	char x;
	int flag=1,flag1=1;
	sqstack *s;
	init_sqstack(s);
	while(cin>>x){
		if(x=='('){
			flag=push_sqstack(s,x);
		}
		if(x==')'){
			flag1=pop_sqstack(s,&x);
		}
	}
	if(empty(s)&&flag==1&&flag1==1)return 1;
	else return -1;
}

int main()
{
    int flag;
    flag=result();
    if(flag==1)
        printf("1");
    else printf("0");
    return 0;
}

/** 
	0为不匹配 1为匹配 输入的时候按Ctrl+Z结束输入

*/