LeetCode | 20. 有效的括号

LeetCode | 20. 有效的括号

OJ链接

• 这道题可以使用栈来解决问题~~

---

思路：

• 首先我们要使用我们之前写的栈的实现来解决此问题~~
• 如果左括号，就入栈
• 如果右括号，出栈顶的左括号跟右括号判断是否匹配
  • 如果匹配，继续
  • 如果不匹配，终止

代码如下：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	//top 表示指向栈顶元素
	//ps->top = -1;
	//top 表示指向栈顶元素的下一个
	ps->top = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("relloc fail!\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
// 获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
// 销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}



bool isValid(char* s) {
    ST st;
    StackInit(&st);

    while(*s)
    {
        switch(*s)
        {
            case ')':
            case ']':
            case '}':
            {
                if(StackEmpty(&st))
                {
                    StackDestroy(&st);
                    return false;
                }
                char top = StackTop(&st);
                StackPop(&st);
                if((*s == ')' && top != '(')
                || (*s == ']' && top != '[')
                || (*s == '}' && top != '{'))
                {
                    StackDestroy(&st);
                    return false;
                }
                else
                {
                    ++s;
                }
                break;
            }
            case '(':
            case '[':
            case '{':
            {
                StackPush(&st,*s);
                ++s;
                break;
            }
            default:
                break;
        }
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}
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
116
117
118
119
120
121
122
123