忘了
0%

利用栈规则做就近括号匹配

Posted on In

利用栈规则做就近括号匹配

从第一个字符开始扫描
当遇见普通字符时忽略，
当遇见左括号时压入栈中
当遇见右括号时从栈中弹出栈顶符号，并进行匹配
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错
结束：
成功: 所有字符扫描完毕，且栈为空
失败：匹配失败或所有字符扫描完毕但栈非空

FILE1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#ifndef _SEQSTACK_H
#define _SEQSTACK_H

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

#define  MAX 1024

struct SStack {
    void *data[MAX];  //栈的数组
    int m_Size; //栈大小
};

typedef void *SeqStack;

//初始化栈
SeqStack init_SeqStack();

//入栈
void push_SeqStack(SeqStack stack, void *data);

//出栈
void pop_SeqStack(SeqStack stack);

//返回栈顶
void *top_SeqStack(SeqStack stack);

//返回栈大小
int size_SeqStack(SeqStack stack);

//判断栈是否为空
bool isEmpty_SeqStack(SeqStack stack);

//销毁栈
void destroy_SeqStack(SeqStack stack);


#endif //_SEQSTACK_H

FILE2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "SeqStack.h"


//初始化栈
SeqStack init_SeqStack() {
    struct SStack *myStack = malloc(sizeof(struct SStack));

    if (myStack == NULL) {
        return NULL;
    }

    //初始化数组
    memset(myStack->data, 0, sizeof(void *) * MAX);

    //初始化栈大小
    myStack->m_Size = 0;

    return myStack;
}

//入栈
void push_SeqStack(SeqStack stack, void *data) {
    //入栈本质  --- 数组尾插
    if (stack == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }

    struct SStack *mystack = stack;
    if (mystack->m_Size == MAX) {
        return;
    }

    mystack->data[mystack->m_Size] = data;

    mystack->m_Size++;
}

//出栈
void pop_SeqStack(SeqStack stack) {
    //出栈本质  --- 数组尾删
    if (stack == NULL) {
        return;
    }

    struct SStack *mystack = stack;

    if (mystack->m_Size == 0) {
        return;
    }

    mystack->data[mystack->m_Size - 1] = NULL;

    mystack->m_Size--;

}

//返回栈顶
void *top_SeqStack(SeqStack stack) {
    if (stack == NULL) {
        return NULL;
    }

    struct SStack *mystack = stack;

    if (mystack->m_Size == 0) {
        return NULL;
    }
    return mystack->data[mystack->m_Size - 1];
}

//返回栈大小
int size_SeqStack(SeqStack stack) {
    if (stack == NULL) {
        return -1;
    }

    struct SStack *mystack = stack;

    return mystack->m_Size;

}

//判断栈是否为空
bool isEmpty_SeqStack(SeqStack stack) {
    if (stack == NULL) {
        return true;//返回-1代表真  空栈
    }

    struct SStack *mystack = stack;

    if (mystack->m_Size == 0) {
        return true;
    }

    return false; //返回0 代表 不是空栈

}

//销毁栈
void destroy_SeqStack(SeqStack stack) {
    if (stack == NULL) {
        return;
    }

    free(stack);
    stack = NULL;
}


FILE3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
int isLeft(char ch) {
    return ch == '(';
}

int isRight(char ch) {
    return ch == ')';
}


static void test01() {

    char *str = "123*(was)s(sd)sdb(fs())())))(()";

    char *p = str;

    SeqStack *stack = init_SeqStack();

    while (*p != '\0') {

        //如果是左括号，入栈
        if (isLeft(*p)) {
            push_SeqStack(stack, p);
        } else if (isRight(*p)) {
            if (size_SeqStack(stack) > 0) {
                pop_SeqStack(stack);
            } else {
                error(str, "Error!", p);

                break;
            }
        }

        p++;
    }

    while (size_SeqStack(stack) > 0) {

        error(str, "Error", top_SeqStack(stack));
        pop_SeqStack(stack);
    }

    destroy_SeqStack(stack);

    stack = NULL;

    bool b = isEmpty_SeqStack(stack);

    printf("\n=-=-=-=-=-=-=-====-=-=\n%d\n",b);


}

static void error(char *str, char *string, const char *p) {

    printf("\n%s\n", string);

    printf("%s\n", str);

    int num = (int) (p - str);

    for (int i = 0; i < num; i++) {
        printf(" ");
    }

    printf("I");

}


int main(int argc, char *argv[]) {

    test01();

    bool b = true;

    printf("%d\n", b);


    return 0;
}