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

【问题描述】
编写一程序检查C源程序文件中{}、()等括号是否匹配,并输出第一个检测到的不匹配的括号及所对应括号所在的行号(程序中只有一个括号不匹配)。
注意：
1.     除了括号可能不匹配外，输入的C源程序无其它语法错误；
2.     字符常量、字符串常量及注释中括号不应被处理，注释包括单行注释//和多行/* */注释
3. 字符和字符串常量中不包含特殊的转义字符(\’,\”)
5. 程序中出现有意义括号的个数不超过200个
不匹配判断规则：
1. 当遇到一个不匹配的右括号(’)’或’}’)时，输出该右括号及所在行号；
2. 当程序处理完毕时，还存在不匹配的左括号时，输出该左括号及所在行号。
【输入形式】
打开当前目录下文件example.c，查体其括号是否匹配。
【输出形式】
若存在括号不匹配时，应输出首先能判断出现不匹配的括号及其所在的行号。当出现括号不匹配时，按下面要求输出相关信息：
without maching  at line 
其中为‘{’, ‘}’， ‘(’, ‘)’等符号，为该符号所在的行号。
若整个程序括号匹配，则按下面所示顺序输出括号匹配情况，中间没有空格。
(){(()){}}
【样例输入1】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }\n”); // }
)
【样例输出1】
without maching ‘)’ at line 4
【样例输入2】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }d\n”); /* }*/
【样例输出2】
without maching ‘{‘ at line 2
【样例输入3】
若当前目录下输入文件example.c中内容如下：
#include
int main(){
printf(“{ hello world }d\n”); /* }*/
}
【样例输出3】
(){()}
【样例说明】
样例1：在注释部分和字符串中的括号不考虑，在将程序处理之后得到的括号序列是(){())，遇到右括号时与最近的左括号匹配，发现最后一个小括号和大括号不匹配。
样例2：处理之后的括号序列是(){()，在最后缺少了右大括号，那么应该输出与之相对应的左括号不匹配。#include 
#include 
void ERROR(char b, int l, int *e)
{
(*e)++;
printf("without maching '%c' at line %d\n",b,l);
}
int main()
{
FILE *fin;
int tmp;
int linenum[1000];
char bracket_stack[500], bracket_w_stack[1000];
int  iter_bstack = -1, iter_w_bstack = -1, error = 0, line = 1;
fin = fopen("example.c", "r");
if (fin == NULL) exit(1);
for (;;)
{
tmp = fgetc(fin);
if (tmp == EOF) break;
else if (tmp == '\n') line++;
else if (tmp == '"')
{
for (;;)
{
tmp = fgetc(fin);
if(tmp=='\\') tmp = fgetc(fin);
else if (tmp == '"') break;
}
}
else if (tmp == '\'')
{
for (;;)
{
tmp = fgetc(fin);
if (tmp == '\\') tmp = fgetc(fin);
else if (tmp == '\'') break;
}
}
else if (tmp == '/')
{
tmp = fgetc(fin);
if (tmp == '/')
{// single-line comment
while ((tmp = fgetc(fin)) != '\n');
line++;
}
else if (tmp == '*')
{// multi-line comment
int flag = 0;
tmp = fgetc(fin);
if (tmp == '\n') line++;
for (;;)
{
if (flag) break;
while (tmp != '*')
{
tmp = fgetc(fin);
if (tmp == '\n') line++;
}
tmp = fgetc(fin);
if (tmp == '\n') line++;
if (tmp == '/') flag = 1;
}
}
else if (tmp == '(')
{
bracket_stack[++iter_bstack] = tmp;
bracket_w_stack[++iter_w_bstack] = tmp;
linenum[iter_bstack] = line;
}
}
else if (tmp == '(' || tmp == '{')
{
bracket_stack[++iter_bstack] = tmp;
bracket_w_stack[++iter_w_bstack] = tmp;
linenum[iter_bstack] = line;
}
else if (tmp == ')')
{
bracket_w_stack[++iter_w_bstack] = tmp;
linenum[iter_bstack] = line;
int leap = 0;
while (leap <= iter_bstack && bracket_stack[iter_bstack - leap] != '(') leap++;
if (iter_bstack<0 || leap) ERROR(tmp, line, &error);
if (leap <= iter_bstack)
{
int i;
for (i = iter_bstack - leap; i < iter_bstack; i++)
{
bracket_stack[i] = bracket_stack[i + 1];
linenum[i] = linenum[i + 1];
}
iter_bstack--;
}
}
else if (tmp == '}')
{
bracket_w_stack[++iter_w_bstack] = tmp;
linenum[iter_bstack] = line;
int leap = 0;
while (leap <= iter_bstack && bracket_stack[iter_bstack - leap] != '{') leap++;
if (iter_bstack<0 || leap) ERROR(tmp, line, &error);
if (leap <= iter_bstack)
{
int i;
for (i = iter_bstack - leap; i < iter_bstack; i++)
{
bracket_stack[i] = bracket_stack[i + 1];
linenum[i] = linenum[i + 1];
}
iter_bstack--;
}
}
else continue;
}
bracket_w_stack[++iter_w_bstack] = '\0';
while (!error && iter_bstack >= 0)
{
ERROR(bracket_stack[iter_bstack], linenum[iter_bstack], &error);
iter_bstack--;
}
if(!error) printf("%s", bracket_w_stack);
fclose(fin);
return 0;
}

主要思路：

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

/*-------------------------------------------------------
功能：可进行括号匹配，输入可包括{}, [], (), 其他任意字符
输入示例：
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;
}

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

#define bool int

bool checkBracketPair(const char* str)
{
	int count = 0;

	while(*str != '\0')
	{
		if(*str == '(')
		{
			count++;
		}
		else if(*str == ')')
		{
			count--;

			if(count<0)  // "))((" or "())"
				break;
		}

		str++;
	}
	//printf("count = %d\n",count);

	if(count == 0)
		return 1; //pair
	else
		return 0; //not pair

}


int main(void)
{
	char str[100]="( ((1)) ((2) (3)) )";

	printf("bracket is %s! [\"%s\"]\n", (checkBracketPair(str)==1)? ("pair"):("not pair"), str);

	return 0;
}