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

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

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

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
#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
#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;
}