題目來源：力扣

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)鐵西免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了1000多家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

題目描述：

給定一個只包括?'('，')'，'{'，'}'，'['，']'的字符串?s，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應(yīng)的相同類型的左括號。

示例 1：

輸入：s = "()"
輸出：true

示例?2：

輸入：s = "()[]{}"
輸出：true

示例?3：

輸入：s = "(]"
輸出：false

提示：

• 1<= s.length<= 104
• s僅由括號?'()[]{}'組成

思路：

根據(jù)s當(dāng)前位置字符來判斷操作，若s為左括號，入棧，若s為右括號，取棧頂元素并且出棧，然后用棧頂元素和s比較，若匹配，則說明當(dāng)前括號對應(yīng)，程序繼續(xù)執(zhí)行，否則錯誤

代碼：

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//銷毀
void StackPush(ST* ps,STDataType x);//入棧
void StackPop(ST* ps);//出棧
STDataType StackTop(ST* ps);//返回棧頂元素
void StackSize(ST* ps);//計(jì)算數(shù)據(jù)個數(shù)
bool StackEmpty(ST* ps);//判斷是否為空
void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
void StackDestory(ST* ps)//銷毀
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)//入棧
{
	assert(ps);
	if (ps->top == ps->capacity) {//滿了擴(kuò)容
		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		else {
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	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];
}
void StackSize(ST* ps)//計(jì)算數(shù)據(jù)個數(shù)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)//判斷是否為空
{
	assert(ps);
	return ps->top == 0;
}
bool isValid(char * s){
      ST st;
      char top;
      StackInit(&st);
      while(*s != '\0'){
          switch(*s){
            case '(':
            case '{':
            case '[':
                 StackPush(&st,*s);
                 s++;
                 break;
            case ')':
            case '}':
            case ']':
            if(StackEmpty(&st)){
                StackDestory(&st);
                return false;
            }
               top = StackTop(&st);
               StackPop(&st);
               if((*s==')' && top != '(') ||
               (*s==']' && top != '[') ||
               (*s=='}' && top != '{'))
               {
                   StackDestory(&st);
                   return false;
               }else{
                   s++;
               }
               break;
               default:
               break;
         }
       }
     bool ret =StackEmpty(&st);
      StackDestory(&st);
      return ret;
}

注意：1.返回之前要釋放內(nèi)存，否則會有內(nèi)存泄漏情況（這是好的習(xí)慣，與題無關(guān)）

2.如果只輸入左括號，我們就無法取棧頂元素然后比較，所以結(jié)尾要加上判空，如果不為空，說明棧內(nèi)還有左括號，沒有匹配完成，返回false

3.如果只輸入右括號，會導(dǎo)致程序出錯，所以在取棧頂元素前要判斷棧是否為空，為空則說明棧內(nèi)無對應(yīng)左括號，返回flase

4.使用完一次s后要記得s++

運(yùn)行結(jié)果：

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：20.有效的括號-C語言-創(chuàng)新互聯(lián)
網(wǎng)頁路徑：http://weahome.cn/article/dihjjd.html