栈实现括号匹配问题：未闭合括号错误位置输出异常

问题分析 #

当前代码的核心问题是栈中仅存储左括号字符，未记录其对应的索引位置。当表达式遍历结束后，栈中剩余的未闭合左括号只能以字符形式弹出，无法获取其原始位置，导致错误输出表达式末尾的索引（41），而不是实际未闭合括号的位置（34）。

修复方案 #

将栈的存储内容从括号字符改为左括号的索引，这样遍历结束后，栈中剩余的索引就是未闭合左括号的准确位置。具体修改如下：

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

// 修改栈元素类型为int，存储括号的索引
typedef int element;
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
}StackType;

void init_stack(StackType* s) {
    s->top = -1;
}

int is_empty(StackType* s) {
    return (s->top == -1);
}

int is_full(StackType* s) {
    return (s->top == (MAX_STACK_SIZE - 1));
}

void push(StackType* s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "Stack Flow Error\n");
        return;
    }
    
    else {
        s->data[++(s->top)] = item;
    }
}

element pop(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Blank Error\n");
        exit(1);
    }

    else {
        return s->data[(s->top)--];
    }
}

element peek(StackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Blank Error\n");
        exit(1);
    }

    else {
        return s->data[s->top];
    }
}

int check_matching(const char* in) {
    StackType s;
    char ch;
    int n = strlen(in);
    init_stack(&s);

    int fail_pos[MAX_STACK_SIZE] = { 0, };
    int fail_cnt = 0;

    for (int i = 0; i < n; i++) {
        ch = in[i];

        if (ch == ' ') {
            continue;
        }

        switch (ch) {
        case '(': case '[': case '{':
            // 压入当前左括号的索引，而非字符
            push(&s, i);
            break;

        case ')': case ']': case '}':
            if (is_empty(&s)) {
                // 无匹配的左括号，记录当前右括号的索引
                fail_pos[fail_cnt++] = i;
                break;
            }

            else {
                // 弹出左括号的索引，通过原字符串获取括号类型
                int open_idx = pop(&s);
                char open_ch = in[open_idx];

                if ((open_ch == '(' && ch != ')') || 
                    (open_ch == '[' && ch != ']') || 
                    (open_ch == '{' && ch != '}')) {
                    // 括号不匹配，记录当前右括号的索引
                    fail_pos[fail_cnt++] = i;
                    break;
                }
            }
        }
    }

    // 栈中剩余的索引都是未闭合的左括号位置
    while (!is_empty(&s)) {
        fail_pos[fail_cnt++] = pop(&s);
    }

    if (fail_cnt > 0) {
        printf("%s : Failed ", in);

        for (int i = 0; i < fail_cnt; i++) {
            // 输出位置从1开始计数
            printf("%d ", fail_pos[i] + 1);
        }

        printf("\n");
        return 0;
    }

    printf("%s : Complete\n", in);
    return 1;
}

int main()
{
    char* expr = "A(x) = 24.5 * (x + func(x, y)) * (r * r * 3.14  / [7 % 10 * sqrt(25)];";

    check_matching(expr);

    return 0;
}

关键修改点 #

1. 栈元素类型修改：将typedef char element;改为typedef int element;，用于存储括号在字符串中的索引位置。
2. 左括号入栈逻辑：遇到左括号时，压入当前索引i而非括号字符。
3. 括号匹配判断：弹出左括号索引后，通过原字符串in[open_idx]获取左括号类型，再与当前右括号匹配。
4. 未闭合括号处理：遍历结束后，栈中剩余的索引直接作为未闭合左括号的位置存入错误数组。

运行结果 #

修改后运行代码，输出与期望一致：

A(x) = 24.5 * (x + func(x, y)) * (r * r * 3.14 / [7 % 10 * sqrt(25)]; : Failed 34

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