CB2-判断表达式中圆括号是否配对¶

代码实现¶

C
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000  // 栈的最大容量

/**
 * 栈的顺序存储结构定义
 */
typedef struct {
    char data[MAXSIZE];  // 存储栈元素的数组
    int top;            // 栈顶指针
} Stack;

/**
 * 判断表达式中圆括号是否配对
 * @param A 字符串表达式
 * @return 括号配对返回true，不配对返回false
 */
bool fun(char A[]) {
    // 初始化栈
    Stack s;
    s.top = -1;

    // 遍历表达式中的每个字符
    for (int i = 0; A[i] != '\0'; i++) {
        // 如果是左圆括号，入栈
        if (A[i] == '(') {
            // 检查栈是否已满
            if (s.top == MAXSIZE - 1) {
                printf("栈溢出\n");
                return false;
            }
            s.data[++s.top] = '(';
        }
        // 如果是右圆括号，检查配对
        else if (A[i] == ')') {
            // 检查栈是否为空（没有对应的左括号）
            if (s.top == -1) {
                return false;  // 右括号多余
            }
            s.top--;  // 匹配成功，出栈
        }
        // 其他字符忽略
    }

    // 最后检查栈是否为空
    if (s.top == -1) {
        return true;   // 所有括号都配对
    } else {
        return false;  // 左括号多余
    }
}

算法执行流程图解¶

正确配对示例：¶

Text Only

表达式："(a+b)*(c-d)"

执行过程：
i=0: '(' → 入栈：栈['('], top=0
i=1: 'a' → 忽略
i=2: '+' → 忽略
i=3: 'b' → 忽略
i=4: ')' → 出栈：栈[], top=-1
i=5: '*' → 忽略
i=6: '(' → 入栈：栈['('], top=0
i=7: 'c' → 忽略
i=8: '-' → 忽略
i=9: 'd' → 忽略
i=10:')' → 出栈：栈[], top=-1

结束：top=-1，返回true

错误配对示例1（右括号多余）：¶

Text Only

表达式："(a+b))"

执行过程：
i=0: '(' → 入栈：栈['('], top=0
i=1: 'a' → 忽略
i=2: '+' → 忽略
i=3: 'b' → 忽略
i=4: ')' → 出栈：栈[], top=-1
i=5: ')' → 栈空，返回false

错误配对示例2（左括号多余）：¶

Text Only
1 2 3 4 5 6 7 8 9	`表达式："(a+b" 执行过程： i=0: '(' → 入栈：栈['('], top=0 i=1: 'a' → 忽略 i=2: '+' → 忽略 i=3: 'b' → 忽略结束：top=0≠-1，返回false`

算法状态变化图解¶

Text Only

表达式："( ( a + b ) * ( c - d ) )"

栈状态变化：
初始：     []              top=-1
'('：     ['(']           top=0
'('：     ['(']['(']      top=1
')'：     ['(']           top=0
'('：     ['(']['(']      top=1
')'：     ['(']           top=0
')'：     []              top=-1

最终top=-1，括号配对正确

复杂度分析¶

时间复杂度：O(n)¶

遍历时间：需要遍历整个字符串一次，O(n)
栈操作：每次入栈/出栈操作O(1)
总体时间复杂度：O(n)

空间复杂度：O(n)¶

栈空间：最坏情况下所有左括号都入栈，O(n)
辅助变量：常数个变量，O(1)
总体空间复杂度：O(n)

多种括号类型拓展版本¶

C
/**
 * 判断表达式中多种类型括号是否配对
 * 支持：圆括号()、方括号[]、花括号{}
 * @param A 字符串表达式
 * @return 括号配对返回true，不配对返回false
 */
bool fun_multiple(char A[]) {
    Stack s;
    s.top = -1;

    for (int i = 0; A[i] != '\0'; i++) {
        char ch = A[i];

        // 如果是左括号，入栈
        if (ch == '(' || ch == '[' || ch == '{') {
            if (s.top == MAXSIZE - 1) {
                printf("栈溢出\n");
                return false;
            }
            s.data[++s.top] = ch;
        }
        // 如果是右括号，检查配对
        else if (ch == ')' || ch == ']' || ch == '}') {
            // 检查栈是否为空
            if (s.top == -1) {
                return false;
            }

            // 检查括号类型是否匹配
            char top_ch = s.data[s.top];
            if ((ch == ')' && top_ch == '(') ||
                (ch == ']' && top_ch == '[') ||
                (ch == '}' && top_ch == '{')) {
                s.top--;  // 匹配成功，出栈
            } else {
                return false;  // 类型不匹配
            }
        }
        // 其他字符忽略
    }

    // 检查是否所有括号都已配对
    return (s.top == -1);
}

优化版本（使用辅助函数）¶

C
/**
 * 判断是否为左括号
 */
bool isLeftBracket(char ch) {
    return (ch == '(' || ch == '[' || ch == '{');
}

/**
 * 判断是否为右括号
 */
bool isRightBracket(char ch) {
    return (ch == ')' || ch == ']' || ch == '}');
}

/**
 * 判断括号是否匹配
 */
bool isMatchingPair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

/**
 * 优化版本的多类型括号匹配
 */
bool fun_optimized(char A[]) {
    Stack s;
    s.top = -1;

    for (int i = 0; A[i] != '\0'; i++) {
        char ch = A[i];

        if (isLeftBracket(ch)) {
            if (s.top == MAXSIZE - 1) return false;
            s.data[++s.top] = ch;
        }
        else if (isRightBracket(ch)) {
            if (s.top == -1) return false;
            if (isMatchingPair(s.data[s.top], ch)) {
                s.top--;
            } else {
                return false;
            }
        }
    }

    return (s.top == -1);
}

更完整的括号匹配检查¶

C
/**
 * 完整版本：提供详细的错误信息
 */
typedef enum {
    VALID,
    EXTRA_LEFT,
    EXTRA_RIGHT,
    MISMATCH
} BracketStatus;

BracketStatus check_brackets_detailed(char A[]) {
    Stack s;
    s.top = -1;

    for (int i = 0; A[i] != '\0'; i++) {
        char ch = A[i];

        if (isLeftBracket(ch)) {
            if (s.top == MAXSIZE - 1) return EXTRA_LEFT;
            s.data[++s.top] = ch;
        }
        else if (isRightBracket(ch)) {
            if (s.top == -1) return EXTRA_RIGHT;
            if (isMatchingPair(s.data[s.top], ch)) {
                s.top--;
            } else {
                return MISMATCH;
            }
        }
    }

    return (s.top == -1) ? VALID : EXTRA_LEFT;
}

测试用例¶

C
/**
 * 测试函数
 */
void test_bracket_matching() {
    char* test_cases[] = {
        "()",           // true
        "()[]{}",       // true
        "([{}])",       // true
        "([)]",         // false - 交叉匹配
        "(((",          // false - 左括号多余
        ")))",          // false - 右括号多余
        "",             // true - 空字符串
        "a+b*(c-d)",    // true - 混合字符
        "({[}])"        // false - 类型不匹配
    };

    int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);

    for (int i = 0; i < num_tests; i++) {
        bool result = fun_multiple(test_cases[i]);
        printf("表达式: %s -> %s\n", 
               test_cases[i], 
               result ? "配对正确" : "配对错误");
    }
}

算法特点¶

核心思想：利用栈的后进先出特性，左括号入栈，右括号时检查栈顶是否为对应的左括号。

关键技巧： 1. 类型匹配：确保括号类型正确对应 2. 数量匹配：确保左右括号数量相等 3. 顺序匹配：确保括号嵌套顺序正确

应用场景： - 编译器语法检查 - 代码编辑器括号高亮 - 数学表达式验证 - XML/HTML标签匹配

易错点： 1. 忘记检查栈空情况 2. 括号类型匹配错误 3. 忽略其他字符的处理 4. 最终栈状态检查遗漏

这种括号匹配算法是栈应用的经典案例，在实际开发中非常实用。