括号匹配问题(0962)

描述

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

input

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

output

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

样例输入

[([][]())]

样例输出

YES

这道题的思路是遇到左括号就入栈，遇到右括号就让栈顶元素出栈匹配，若匹配成功继续，若不成功则输出NO，若将字符串扫描完毕栈不为空，则说明匹配不成功

代码如下

#include<iostream>
#include<algorithm>
#include<memory.h>
#include<string.h>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
 
#define N 100
struct Stack {
    char date[N];
    int top;
} stack;
//栈初始化
void init(Stack *stack) {
    stack->top=-1;
    memset(stack->date,0,sizeof(char)*N);//数据清零
}
 
bool isempty(Stack*stack) { //判断是否为空
return stack->top==-1;
}
bool isfull(Stack*stack)//判断栈溢出
{
return stack->top==N-1;
}
int gettop(Stack*stack)//获取栈顶
{
return stack->date[stack->top];
}
void push(Stack*stack,char a)//压栈
{
    if(isfull(stack)){
        return;
    }else{
        stack->top++;
        stack->date[stack->top]=a;
    }
     
}
void pop(Stack*stack)//吐
{
if(isempty(stack)){
    return;
}else{
    stack->top--;
}
}
bool isleft(char a){
    return (a=='(')||(a=='[');
}
bool isright(char a){
    return (a==']')||(a==')');
}
bool juge(char a,char b){
    return (a=='('&&b==')')||(a=='['&&b==']');
}
int main(){
    Stack stack;
    init(&stack);
    char str[100];
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(isleft(str[i])){
            push(&stack,str[i]);
        }else {
        if(isright(str[i])){
        if(!juge(stack.date[stack.top],str[i])){
            cout<<"NO";
            return 0;
        }
        pop(&stack);
        }
        }
    }
    cout<<"YES";
    return 0;
}