原題鏈接：https://leetcode.cn/problems/valid-parentheses/

目錄

1. 題目描述

2. 思路分析

3. 代碼實現

---

1. 題目描述

?

2. 思路分析

這道題目主要考查了棧的特性：

題目的意思主要是要做到3點匹配：類型、順序、數量。

題目給的例子是比較簡單的情況，可能還有如下較為復雜的情況：

循環遍歷字符串s中的字符，逐個取到每個括號，如果該括號是：

1. 左括號，入棧
2.?右括號，出棧頂括號，進行匹配。

?如果不匹配，直接返回false。否則繼續循環。

?循環結束后，如果棧空則匹配，否則左括號比右括號多肯定不匹配。

3. 代碼實現

typedef char STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{STDataType* a;int top;  //棧頂int capacity;  //容量
}ST;//初始化棧
void STInit(ST* ps);
//入棧
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);
//獲取棧中有效元素個數
int STSize(ST* ps);
//檢測棧是否為空
bool STEmpty(ST* ps);
//銷毀棧
void STDestroy(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);//空assert(ps->a > 0);--ps->top;
}STDataType STTop(ST* ps)
{assert(ps);//空assert(ps->a > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STDestroy(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}bool isValid(char * s){ST st;STInit(&st);char topVal;while(*s){if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{if(STEmpty(&st)){STDestroy(&st);return false;}topVal=STTop(&st);if(*s==')'&&topVal!='('||*s=='}'&&topVal!='{'||*s==']'&&topVal!='['){STDestroy(&st);return false;}else{STPop(&st);}}++s;}bool ret=STEmpty(&st);STDestroy(&st);return ret;
}

?