力扣網 20 有效的括號

題目描述

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

有效字符串需滿足：

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

示例 1：

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

示例?2：

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

示例?3：

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

思路分析

如果這里再用所謂的遍歷字符串尋找進行匹配的話，時間復雜度高且不說，還麻煩，但如果我們學習棧了以后，這道題會變得異常輕松。

我們將所有的左括號入棧，在字符串里找右括號，同時出棧左括號進行匹配，如果匹配成功就返回true，否則返回false。

注意的問題：

這里除了括號類型的匹配問題，同時還有數量問題，會存在左括號多于右括號或者反過來的情況，這里如果數量不匹配的話也返回false。

判斷數量的問題，再尋找右括號時，先判斷棧是否為空，這是判斷右括號多余左括號的情況，

在遍歷一遍字符串后，如果棧里面還有括號，說明左括號多于右括號，也返回false。

完整代碼

力扣環境下是不提供棧的，這里我們需要自己定義。

棧定義和常用接口

頭文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef char STDataType;typedef struct Stack
{STDataType* a;int _top;int _capacity;
}Stack;// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);

?接口實現文件

#include"Stack.h"// 初始化棧
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->_capacity = 0;ps->_top = 0;
}// 入棧
void StackPush(Stack* ps, STDataType data)
{assert(ps);//檢查是否棧滿if (ps->_top == ps->_capacity){int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;Stack* ptr = realloc(ps->a, sizeof(STDataType) * newcapacity);if (ptr == NULL){perror("realloc fail");return;}ps->a = ptr;ps->_capacity = newcapacity;}//入棧ps->a[ps->_top] = data;ps->_top++;
}// 出棧
void StackPop(Stack* ps)
{assert(ps);assert(ps->_top > 0);ps->_top--;
}// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top > 0);return ps->a[ps->_top-1];
}// 獲取棧中有效元素個數
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
int StackEmpty(Stack* ps)
{assert(ps);if (ps->_top == 0){return 1;}else{return 0;}
}// 銷毀棧
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->_capacity = 0;ps->_top = 0;
}

題目所需代碼

bool isValid(char* s) {Stack st;StackInit(&st);//初始化棧while (*s){if (*s == '{' || *s == '(' || *s == '[')//為左括號進棧{StackPush(&st, *s);}else{if (StackEmpty(&st))//如果為右括號，先判斷棧是否為空{StackDestroy(&st);return false;}char top = StackTop(&st);//出棧棧頂括號StackPop(&st);if (*s == ']' && top != '[' ||//兩者進行匹配，如果存在不等情況，返回false*s == '}' && top != '{' ||*s == ')' && top != '('){StackDestroy(&st);return false;}}++s;}bool ret = StackEmpty(&st);//最后再判斷棧是否為空（左括號多余右括號情況），布爾值，如果棧為空返回真，否則返回假StackDestroy(&st);return ret;
}

?