962: 括号匹配问题
题目描述
假设表达式中允许包含两种括号:圆括号和方括号。编写一个算法判断表达式中的括号是否正确配对。

输入
由括号构成的字符串，包含”（“、”）“、”[“和”]“。

输出
如果匹配输出YES，否则输出NO。

样例输入
[([])]
样例输出
YES

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

typedef struct 
{
	char data[10000];
	int top;
} SqStack;

void initStrack(SqStack *&s)
{
	s=(SqStack *) malloc(sizeof(SqStack));
	s->top=-1; 
 } 

int isleft(char a) 
{ 
	if(a=='('||a=='[') 
		return 1; 
	else 
		return 0; 
} 
 
int rightleft(char a) 
{ 
	if(a==')'||a==']') 
		return 1; 
	else 
		return 0; 
} 


int KH(SqStack *&s,char a[])
{
	int i,j=0;
	for(i=0;a[i]!='\0';i++)
	{
		if(isleft(a[i])==1)
		{
		s->top++;
		s->data[s->top]=a[i];
		}
		if(rightleft(a[i])==1)
		{
            if(a[i]==')')
            {
                if(s->data[s->top]!='(')
                    return 1;
                s->top--;
            }
            if(a[i]==']')
            {
                if(s->data[s->top]!='[')
                    return 1;
                s->top--;
            }
		}
	}

	if(s->top!=-1)
		return 1;
	return j;
}


void ClearStack(SqStack *&s)
{
	free(s);
}

int main()
{
	SqStack *s;
	char a[1000];
	int k;
	scanf("%s",&a);
	initStrack(s);
	k=KH(s,a);
	if(k==0)
		printf("YES");
	else
		printf("NO");
	ClearStack(s);
}

在这里再贴一个c++的代码，不得不感慨c++写数据结构题确实舒服的多

#include <bits/stdc++.h>
using namespace std;

int main()
{
    char s[500];
    cin>>s;
    stack <char> p;
    int ls=strlen(s),i;
    bool flag=true;
    for(i=0;i<ls;i++)
    {
        if(s[i]=='['||s[i]=='(')
            p.push(s[i]);
        else
        {
            if(p.empty())
            {
                cout<<"NO";
                flag=false;
                break;
            }
            else
            {
                if((s[i]==']'&&p.top()=='[')||(s[i]==')'&&p.top()=='('))
                    p.pop();
            }
        }
    }
    if(flag)
    {
        if(p.empty())
            cout<<"YES";
        else
            cout<<"NO";
    }
    return 0;
}