利用栈，实现括号匹配功能

利用栈，实现括号匹配功能，例:"()"匹配成功，"([]"匹配失败

main.c

#include "stack.h"


int main() {
    char testCases[][MAX_LENGTH] = {
        "()", "(]", "([)]", "{[]}", "((())", ""
    };
    int numCases = sizeof(testCases) / sizeof(testCases[0]);
    
    for (int i = 0; i < numCases; i++) {
        printf("表达式 '%s': %s\n", 
               testCases[i], 
               isBalanced(testCases[i]) ? "匹配成功" : "匹配失败");
    }
    
    return 0;
}    

stack.h

#ifndef __STACK_H__
#define __STACK_H__

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

#define MAX_LENGTH 100

typedef struct {
    char data[MAX_LENGTH];
    int top;
} Stack;

void initStack(Stack *s);
bool isEmpty(Stack *s);
bool push(Stack *s, char c);
bool push(Stack *s, char c);
bool peek(Stack *s, char *c);
bool isLeftBracket(char c);
bool isRightBracket(char c);
bool isMatchingPair(char left, char right) ;
bool isBalanced(char *expression);


#endif

stack.c

#include "stack.h"



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

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 入栈操作
bool push(Stack *s, char c) {
    if (s->top >= MAX_LENGTH - 1) {
        return false; // 栈溢出
    }
    s->data[++(s->top)] = c;
    return true;
}

// 出栈操作
bool pop(Stack *s, char *c) {
    if (isEmpty(s)) {
        return false; // 栈为空
    }
    *c = s->data[(s->top)--];
    return true;
}

// 获取栈顶元素
bool peek(Stack *s, char *c) {
    if (isEmpty(s)) {
        return false; // 栈为空
    }
    *c = s->data[s->top];
    return true;
}

// 判断字符是否为左括号
bool isLeftBracket(char c) {
    return c == '(' || c == '[' || c == '{';
}

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

// 判断左右括号是否匹配
bool isMatchingPair(char left, char right) {
    switch (left) {
        case '(': return right == ')';
        case '[': return right == ']';
        case '{': return right == '}';
        default: return false;
    }
}

// 检查表达式括号是否匹配
bool isBalanced(char *expression) {
    Stack s;
    initStack(&s);
    int len = strlen(expression);
    
    for (int i = 0; i < len; i++) {
        char c = expression[i];
        if (isLeftBracket(c)) {
            if (!push(&s, c)) {
                printf("错误：栈溢出\n");
                return false;
            }
        } else if (isRightBracket(c)) {
            char topChar;
            if (!pop(&s, &topChar)) {
                return false; // 没有匹配的左括号
            }
            if (!isMatchingPair(topChar, c)) {
                return false; // 括号类型不匹配
            }
        }
    }
    
    return isEmpty(&s); // 栈为空表示所有括号都匹配
}

makefile

EXE=stack
Objs=$(patsubst %.c,%.o,$(wildcard *.c))
CC=gcc
CFlags=-c -o

all:$(EXE)
$(EXE):$(Objs)
    $(CC) $^ -o $@
%.o:%.c
    $(CC) $^ $(CFlags) $@
.PHONY:clean                                   
clean:
    rm $(EXE) $(Objs)