有效的括号

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/valid-parentheses/description/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

栈（后进先出）

这是由于创建栈错误而引发的报错。

初始化：

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;
}

创建栈：

ST st;

ps是一个指针变量接收的是st的地址。

使用c语言实现：

typedef char 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);int StackSize(ST* ps);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->capacity = ps->top = 0;
}
//入栈
void StackPush(ST* ps, STDataType x) {assert(ps);if (ps->top == ps->capacity) {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];
}
//返回栈中的数据个数
int StackSize(ST* ps) {assert(ps);return ps->top;
}bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0;
}bool isValid(char* s) {ST st;StackInit(&st);while(*s ){switch(*s){case '[':case'{':case'(':{StackPush(&st,*s);++s;break;}case']':case'}':case')':{if(StackEmpty(&st)){StackDestory(&st);return false;}char 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;
}

注意栈的销毁，否则容易内存泄漏。

最优写法（c++）：

class Solution {
public:bool isValid(string s) {stack<int> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(' || s[i] == '[' || s[i] == '{') st.push(i);else {if (st.empty()) return false;if (s[i] == ')' && s[st.top()] != '(') return false;if (s[i] == '}' && s[st.top()] != '{') return false;if (s[i] == ']' && s[st.top()] != '[') return false;st.pop();}}return st.empty();}
};