求解K&R习题1-24：括号匹配类语法错误检测难题

核心思路：用栈处理嵌套匹配 #

括号、方括号、大括号的嵌套匹配本质是后进先出逻辑，栈刚好能完美解决：

• 遇到左括号((、[、{)，直接压入栈
• 遇到右括号()、]、})，检查栈顶是否是对应的左括号：
  • 匹配则弹出栈顶
  • 不匹配或栈为空，直接标记错误
• 遍历完程序后，栈不为空说明存在未闭合的左括号，同样是错误

必须处理的特殊场景 #

1. 引号内的括号忽略 #

单引号'或双引号"里的括号只是普通字符，不算语法符号：

• 遇到引号时切换到「引号模式」，直到遇到对应的结束引号（注意跳过转义引号\"或\'，不能当作结束标记）

2. 注释内的括号忽略 #

• 遇到/*进入「块注释模式」，直到*/才退出
• 遇到//进入「行注释模式」，直到换行才退出

3. 转义序列处理 #

引号内的转义字符（如\"、\'、\\）要正确识别，避免把转义后的引号当成结束符号

针对嵌套顺序错误的案例分析 #

比如({ ) }：

• 先压入(，再压入{
• 遇到)时，栈顶是{，和)不匹配，直接判定错误

再比如((({(({}})))))：

• 压入一系列左括号后，遇到第一个}，栈顶是{，匹配弹出；接着遇到第二个}，此时栈顶是(，不匹配，判定错误

代码实现框架（C语言） #

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

#define MAX_STACK_SIZE 100

char stack[MAX_STACK_SIZE];
int top = -1;

// 压栈操作
void push(char c) {
    if (top >= MAX_STACK_SIZE - 1) {
        printf("栈溢出：程序嵌套层级过深\n");
        exit(1);
    }
    stack[++top] = c;
}

// 弹栈操作
char pop() {
    if (top < 0) {
        return '\0'; // 返回空字符表示栈空
    }
    return stack[top--];
}

// 检查左右括号是否匹配
int is_match(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

int main() {
    int c;
    int in_quote = 0;       // 0: 不在引号内, 1: 单引号模式, 2: 双引号模式
    int in_comment = 0;     // 0: 不在注释内, 1: 块注释模式, 2: 行注释模式
    int line_num = 1;

    while ((c = getchar()) != EOF) {
        // 处理行注释：直到换行退出
        if (in_comment == 2) {
            if (c == '\n') {
                in_comment = 0;
                line_num++;
            }
            continue;
        }

        // 处理块注释：直到遇到*/退出
        if (in_comment == 1) {
            if (c == '*') {
                int next_c = getchar();
                if (next_c == '/') {
                    in_comment = 0;
                } else if (next_c != EOF) {
                    ungetc(next_c, stdin); // 把非/的字符放回输入流
                }
            }
            continue;
        }

        // 处理引号内的内容
        if (in_quote) {
            if (c == '\\') { // 跳过转义字符
                getchar();
                continue;
            }
            if ((in_quote == 1 && c == '\'') || (in_quote == 2 && c == '\"')) {
                in_quote = 0;
            }
            continue;
        } else {
            if (c == '\'') {
                in_quote = 1;
            } else if (c == '\"') {
                in_quote = 2;
            }
        }

        // 检测注释起始
        if (c == '/') {
            int next_c = getchar();
            if (next_c == '*') {
                in_comment = 1;
            } else if (next_c == '/') {
                in_comment = 2;
            } else if (next_c != EOF) {
                ungetc(next_c, stdin); // 把非注释的/后续字符放回
                push(c); // 这里的/是普通字符，若需要可以根据需求调整
            }
            continue;
        }

        // 处理左括号
        if (c == '(' || c == '[' || c == '{') {
            push(c);
        }
        // 处理右括号
        else if (c == ')' || c == ']' || c == '}') {
            char left = pop();
            if (!is_match(left, c)) {
                printf("第%d行：括号不匹配，遇到%c，期望匹配的是%c\n", 
                       line_num, c, left ? left : "无对应左括号");
            }
        }

        // 统计行数
        if (c == '\n') {
            line_num++;
        }
    }

    // 检查剩余未闭合的左括号
    while (top >= 0) {
        char left = pop();
        printf("文件结束：存在未闭合的左括号%c\n", left);
    }

    return 0;
}

注意事项 #

• 栈的大小可根据实际需求调整，避免嵌套过深导致溢出
• 转义字符的处理要严谨，确保不会误判引号结束
• 标准C不允许嵌套块注释，所以代码未处理该场景，若需支持可额外扩展逻辑
• 可添加更详细的错误定位信息，比如列号，提升调试效率

内容的提问来源于stack exchange，提问作者hansoko