有效的括号

有效的括号

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

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

有效字符串需满足：

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

示例 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();
    }
};