leetcode 20.有效的括号-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 20.有效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

⭐️ 题目描述

leetcode 20.有效的括号,刷题,leetcode,学习,栈,刷题
🌟 leetcode链接：有效的括号

1️⃣ 代码与思路：

栈问题： 左括号进栈，如果是右括号则拿出栈顶元素比较，相同弹出栈顶元素，接着继续比较，不相同返回 false，还要考虑一些特殊情况，具体看如下代码。

注：由于C语言没有接口，所以手写了一套栈来使用。或者也可以使用静态数组模拟栈。文章来源地址https://www.toymoban.com/news/detail-535747.html


typedef char StackType;

typedef struct Stack {
	StackType* data;	
	int top;			// 栈顶
	int capacity;		// 容量
}Stack;
void StackInit(Stack * ps);
void StackDestroy(Stack * ps);
void StackPush(Stack* ps , StackType node);
void StackPop(Stack* ps);
bool StackEmpty(Stack* ps);
int StackSize(Stack* ps);
StackType StackTop(Stack * ps);

void StackInit(Stack* ps) {
	assert(ps);

	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}


void StackDestroy(Stack* ps) {
	assert(ps);

	free(ps->data);
	ps->top = 0;
	ps->capacity = 0;
}


void StackPush(Stack* ps , StackType node) {
	assert(ps);

	// 检查容量
	if (ps->top == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		StackType* newData = (StackType*)realloc(ps->data , sizeof(StackType) * newCapacity);
		assert(newData);
		ps->data = newData;
		ps->capacity = newCapacity;
	}

	ps->data[ps->top] = node;
	ps->top++;
}

void StackPop(Stack* ps) {
	assert(ps);

	// 判断栈是否为空
	assert(!StackEmpty(ps));

	ps->top--;
}

StackType StackTop(Stack* ps) {
	assert(ps);

	assert(!StackEmpty(ps));

	return ps->data[ps->top - 1];
}

bool StackEmpty(Stack* ps) {
	assert(ps);
	// 空为真，非空返回0
	return ps->top == 0;
}

int StackSize(Stack* ps) {
	assert(ps);

	return ps->top;
}

// 思路：左括号进栈 如果是右括号则拿出栈顶元素比较 以此类推...
bool isValid(char * s){
    Stack st;
    StackInit(&st);

    while (*s) {
        if (*s == '{' || *s == '[' || *s == '(') {
            // 进栈
            StackPush(&st , *s);
            s++;
        } else {
            // 特殊情况：如果栈为空 那么当前的右括号无匹配项 直接返回 fasle
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }

            // 取栈顶元素
            StackType topElement = StackTop(&st);
            // 弹出栈顶元素
            StackPop(&st);
            if ( 
                (topElement == '{' && *s == '}') || 
                (topElement == '(' && *s == ')') ||
                (topElement == '[' && *s == ']')
            ) {
                s++;
            }
            else {
                StackDestroy(&st);
                return false;
            }
        }
    }

    // 如果循环结束 栈是空的 说明括号一对一对抵消了
    // 如果栈里有元素 说明括号没有完全匹配
    bool res = StackEmpty(&st);
    StackDestroy(&st);
    return res;

}