括弧匹配（c語言實現）

⭐ 我的網站: www.mengyingjie.com ⭐

1要求

編寫程式檢查該字元串的括弧是否成對出現，而且不能交叉出現。
輸入：
一個字元串，裡邊可能包含“()”、"{}"、“[]”三種括弧，“#”結束
輸出：
成功：代表括弧成對出現並且嵌套正確
失敗：未正確使用括弧字元。

2分析

用一個棧，就能解決該問題，左括弧棧頂字元必須和第一個入棧的右括弧字元匹配。
棧介紹：棧是一種特殊的線性表，僅能線上性表的一端操作。
棧的特性：後進先出（LIFO)
由於正在學數據結構，於是棧的定義與操作都是自己編寫的，為了鞏固概念

3代碼

#include<stdio.h>
#include <malloc.h>

#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
#define bool int            //自定義bool變數
#define SElemType char

typedef struct {
    SElemType *base;        //棧基地址
    SElemType *top;         //棧頂地址
    int stacksize;
} SqStack;

//------基本操作的演算法描述------
//構建一個空棧
bool InitStack(SqStack *S) {
    S->base = (SElemType *) malloc(STACK_INT_SIZE * sizeof(SElemType)); //開闢新的空間
    if (!S->base) return 0;     //開闢失敗返回0
    S->top = S->base;
    S->stacksize = STACK_INT_SIZE;
    return 1;
}

//若棧不為空，返回棧頂元素，並返回true 否則返回 false
bool GetTop(SqStack S) {
    if (S.top == S.base) return 0;
    return *(S.top - 1);
}

//插入元素 為新的棧頂元素
bool Push(SqStack *S, SElemType e) {
    if (S->top - S->base >= S->stacksize) //如果棧滿  需要增加空間
    {
        S->base = (SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S->base) return 0;
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return 1;
}

//若棧不為空，則刪除棧頂元素，用e返回其值，返回true， 否則返回false
bool Pop(SqStack *S, SElemType *e) {
    if (S->top == S->base) return 0;
    *e = *(--S->top);
    return 1;
}

//檢查括弧字元在字元集中的位置
int CheckChar(char c, char OP[]) {
    int i;
    for (i = 0; i < 3; i++)
        if (c == OP[i])return i;
    return 999;
}

int main() {
    SqStack OPTR;
    InitStack(&OPTR);
    Push(&OPTR, '#');
    printf("輸入括弧以“#”結尾\n");
    char c;
    c = getchar();
    int m = 1;          //判斷最終是否完全匹配   完全匹配  值為1，否則為0
    char OP1[] = {'[', '(', '{'};       //前置括弧字元集
    char OP2[] = {']', ')', '}'};       //後置括弧字元集
    while (c != '#') {
        if (CheckChar(c, OP1) < 3) {
            Push(&OPTR, c);
            c = getchar();
        } else {
            if (CheckChar(GetTop(OPTR), OP1) == CheckChar(c, OP2)) {
                //如果需要檢驗的兩個符號在前置和後置括弧集中的位置相同則表示配對成功
                //例如[和]，[在前置括弧集中的位置1，]在後置括弧集中的位置1，所以匹配成功
                Pop(&OPTR, &c);
                c = getchar();
                continue;
            } else {
                m = 0;
                break;
            }
        }

    }
    if (GetTop(OPTR) != c)m = 0;
    if (m == 1)printf("\n括弧完全匹配！");
    else printf("\n括弧匹配失敗！");
    return 0;
}

遇到此類問題，但看了文章還是未解決，
評論或加 QQ：781378815