括号匹配 分数 35 请编写程序判断一个包含“（”和“）”的括号序列是否匹配。如匹配则输出Match；如不匹配，计算出使该序列变为匹配序列所需添加的最少括号数目（只允许在该序列开始和结尾处添加括号），并输出经添加最少括号后得到的合法匹配序列。 输入格式: 输入为若干行，每行一个字符串，包含不超过10 5 个括号。输入行数不超过10行。 输出格式: 对于输入的每个括号序列输出1行或2行信息。若输入的括号序列匹配，则输出Match。若不匹配，则输出分为2行，第1行为一个整数，表示将该序列变为匹配序列所需添加的最少括号数目，第2行为一个字符串，表示经添加最少括号后得到的合法匹配序列。 输入样例: (())() )( ()))(( 输出样例: Match 2 ()() 4 ((()))(())

以下是判断括号匹配的代码：

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

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;  // 栈顶指针
} Stack;

void initStack(Stack *s) {
    s->top = -1;  // 初始化栈顶指针为-1
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, char c) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->data[++s->top] = c;
}

char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return '\0';
    }
    return s->data[s->top--];
}

int main() {
    char str[MAX_SIZE];
    Stack s;
    int i, len, count = 0;
    printf("Input a string: ");
    scanf("%s", str);
    len = strlen(str);
    initStack(&s);
    for (i = 0; i < len; i++) {
        if (str[i] == '(') {
            push(&s, str[i]);
        } else if (str[i] == ')') {
            if (isEmpty(&s)) {
                count++;
            } else {
                pop(&s);
            }
        }
    }
    if (isEmpty(&s) && count == 0) {
        printf("Match\n");
    } else {
        printf("%d\n", s.top + count + 1);
        printf("%s", str);
        for (i = 0; i < s.top + count; i++) {
            printf(")");
        }
        printf("\n");
    }
    return 0;
}

首先输入一个包含“（”和“）”的括号序列，然后定义一个栈s，如果遇到左括号“（”，就将其入栈；如果遇到右括号“）”，就从栈中弹出一个左括号“（”，如果栈为空，则需要添加一个左括号“（”使其匹配，计数器count加1。最后判断栈是否为空，如果为空，则该括号序列匹配，输出Match；否则，需要添加count + s.top + 1个右括号“）”使其匹配，其中s.top + 1表示栈中剩余的左括号“（”数量，count表示需要添加的左括号“（”数量，输出结果即为添加最少括号后得到的合法匹配序列。