给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

输入格式:
输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。

输出格式:
如果括号配对，输出yes，否则输出no。

输入样例1:
sin(10+20)
输出样例1:
yes
输入样例2:
{[}]
输出样例2:
no

思路：题目输入一些字符串，我们就先保留括号之类的，判断是否匹配。如果遇到左括号，就入栈，如果遇到一个右括号，就与栈顶元素比较，如果匹配，出栈，就继续重复操作，直到字符串没有了。期间一旦出现不匹配的括号对就直接输出no ，如果栈空了，说明匹配了，就输出yes。

#include<stdio.h>
#include<string.h>

int left(char c)//判断是否为左括号，是返回1，否返回0.
{
    if(c=='('||c=='{'||c=='[')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int right(char c)//判断是否为右括号，是返回1，否返回0.
{
    if(c==')'||c=='}'||c==']')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int check(char left,char right)//判断是否左右括号匹配，是返回1，否返回0.
{
    if(left=='('&&right==')')
    {
        return 1;
    }
    
    if(left=='{'&&right=='}')
    {
        return 1;
    }
    
    if(left=='['&&right==']')
    {
        return 1;
    }
    
    return 0;
}

int main()//主函数。
{
    int i=0,l;//定义循环变量i和字符串长度l。
    char stack[200];//定义字符数组存放左括号。
    int top=0;//初始化栈，栈为空，栈顶top=0；
    char s[200];//存放字符串。
    gets(s);//输入字符串到s数组中，数组中除了存放了有字符串，末尾还存放了“/0”，以表示是字符串。
    l=strlen(s);//字符串长度。
    
    for(i=0;i<l;i++)//遍历每个字符串中的字符。
    {
        if(left(s[i])==1)//如果是左括号入栈，同时栈顶向上移动。
        {
            stack[top]=s[i];
            top++;
        }
        else if(right(s[i])==1)//如果是右括号，那么开始在栈中判断是否匹配。
        {
            if(check(stack[top-1],s[i]))//如果匹配，那么栈顶下移，继续执行下一次新的for循环。
            {
                top--;
                continue;
            }
            else//如果不匹配，那么输出no，程序返回0，结束。
            {
                printf("no");
                return 0;
            }
        }
    }
    //如果不是在for循环中结束，那么就需要判断栈是否为空。因为不是在for循环中结束，说明都匹配成功了，但会出现特殊情况比如（（（）），令栈不为空。所以是否括号匹配成功不仅要判断是否右括号都有左括号使其匹配，还需要判断栈是否为空。
    if(top==0)
    {
      printf("yes");
      return 0;
    }
    else
    {
    printf("no");
    return 0;
    }
   
}

主要思路：

1. 主要是借助栈对括号进行匹配，遍历整个字符串，若为左括号，则入栈；若为右括号，则判断栈是否为空，以及栈顶元素与当前元素是否匹配；
2. 要特别注意每个字符串的遍历结束的条件。

/*-------------------------------------------------------
功能：可进行括号匹配，输入可包括{}, [], (), 其他任意字符
输入示例：
3
{{{{{{{[[[[[1314]]]]]}}}}}}}
{{{{{[[[(())]}}}}}
((({{{{{[[521]]}}}}})))
输出示例：
Yes
No
Yes
Author: Zhang Kaizhou
Date:2019-3-6 14:59:06
--------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 1000

typedef struct node{ // 定义一个结点数据类型用于存放每行结果
    char res[10];
    struct node * pnext;
} Node;

typedef struct{ // 定义一个栈数据类型，用于符号判断
    char oper[MAXSIZE];
    int top;
} OperStack;

void judge_blanket_match(char * str, Node * p);
void push_oper(OperStack * p_oper, char ch);
void pop_oper(OperStack * p_oper, char * ch);
void list_tail_insert(Node ** pphead, Node ** pptail, Node * p);
void list_print(Node * phead);

int main(){
    int n, i;
    char str[MAXSIZE] = { '\0' };
    Node * phead = NULL, * ptail = NULL;
    scanf("%d", &n);
    for(i = 0; i < n; i++){ // 循环输入n组测试数据
        scanf("%s", str);
        Node * pnew = (Node *)calloc(1, sizeof(Node)); // 产生一个结点用于存储结果
        judge_blanket_match(str, pnew);
        list_tail_insert(&phead, &ptail, pnew);
    }
    list_print(phead);

    free(phead);
    free(ptail);
    return 0;
}

void judge_blanket_match(char * str, Node * p){
    OperStack * p_oper = (OperStack *)calloc(1, sizeof(OperStack)); // 定义一个栈指针
    p_oper->top = -1; // 初始化栈顶指针
    int flag = 0;
    char temp;
    while(* str != '\0'){ // 遍历整个字符串
        switch(* str){
        case '{':
        case '[':
        case '(':
            push_oper(p_oper, * str); // 左括号直接入栈
            str++;
            break;
        case '}':
            if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '{'){ // 右括号时，若栈非空，判断与栈顶元素是否匹配
                pop_oper(p_oper, &temp); // 若匹配，则出栈栈顶元素
                str++;
                break;
            }else{ // 不匹配，则结果为No，终止循环
                strcpy(p->res, "No");
                flag = 1;
                * str = '\0'; // 终止遍历
                break;
            }
        case ']':
            if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '['){
                pop_oper(p_oper, &temp);
                str++;
                break;
            }else{
                strcpy(p->res, "No");
                flag = 1;
                * str = '\0';
                break;
            }
        case ')':
            if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '('){
                pop_oper(p_oper, &temp);
                str++;
                break;
            }else{
                strcpy(p->res, "No");
                flag = 1;
                * str = '\0';
                break;
            }
        default:
            str++;
            break;
        }
    }
    if(flag == 0 && p_oper->top < 0){
        strcpy(p->res, "Yes");
    }else{
        strcpy(p->res, "No");
    }
    free(p_oper); // 释放操作数栈
    p_oper = NULL; // 原指针置空
    return;
}

void push_oper(OperStack * p_oper, char ch){
    if(p_oper->top == MAXSIZE - 1){
        printf("The operator stack is full!\n");
    }else{
        p_oper->top++;
        p_oper->oper[p_oper->top] = ch;
    }
    return;
}

void pop_oper(OperStack * p_oper, char * ch){
    if(p_oper->top < 0){
        printf("The operator stack is empty!\n");
    }else{
        * ch = p_oper->oper[p_oper->top];
        p_oper->top--;
    }
    return;
}

void list_tail_insert(Node ** pphead, Node ** pptail, Node * p){
    if(* pphead == NULL){
        * pphead = p;
        * pptail = p;
    }else{
        (*pptail)->pnext = p;
        * pptail = p;
    }
    return;
}

void list_print(Node * phead){
    while(phead != NULL){
        puts(phead->res);
        phead = phead->pnext;
    }
    return;
}

C语言括号匹配问题

用C语言实现括号匹配算法。要求输入任意的包含括号的字符序列(不一定是表达式)，都能判断是否匹配。在测试时，要求序列中既有括号，也要有普通字符，括号必须包含( )、[ ]、{ }这三种。

数组栈

代码

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

#define MAX_SIZE 50

typedef char datatype;

datatype stack[MAX_SIZE];

int top = 0, base = 0;

void initial() //初始化
{
    top = base = 0;
}

void push(datatype x) //进栈
{
    stack[top] = x;
}

void pop() //出栈
{
    top--;
}

char top_data() //栈顶元素
{
    return stack[top];
}

int main()
{
    initial();
    datatype str[MAX_SIZE] = {'\0'};
    gets(str);
    char ch[MAX_SIZE] = {'\0'};
    strcpy(ch, str);

    int flag = 1;
    for (int i = 0; ch[i] != '\0'; i++)
    {
        if ((ch[i] == '{') || (ch[i] == '[') || (ch[i] == '('))
        {
            push(ch[i]);
        }
        else if ((ch[i] == '}') || (ch[i] == ']') || (ch[i] == ')'))
        {
            char a;
            a = top_data();
            pop();
            if ((a == '{' && ch[i] == '}') || (a == '(' && ch[i] == ')') || (a == '[' && ch[i] == ']'))
            {
                continue;
            }
            else
                flag = 0;
        }
    }

    if (top != 0)
    {
        flag = 0;
    }

    if (flag == 0)
    {
        printf("FAUSE\n");
    }
    else
        printf("TRUE\n");
    return 0;
}

示例1：
输入: “()”
输出:TRUE

示例2：
输入: “()[]{}”
输出:TRUE

示例3：
输入: “(]”
输出:FAUSE

示例4：
输入: “{[]}”
输出:TRUE