有效的括号（简单）

题目要求

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.注意空字符串可被认为是有效字符串。

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

第一次做，执行了 n 次，执行用时 4ms，内存消耗 9.4MB 菜的一批，先放第一次提交的代码，优化之后再发上来

使用C++栈解决

思路

根据题意进行分析，可以参考编译器中识别 ()、[]、{} 是否成对出现的功能。

理解题目意思后，简单的构思一下问题，这里说的直接一点，当 ’(‘、‘[’、‘{’ 其中一个出现时，就意味着剩下的字符串中必须要存在与之对应的 ’)‘、‘]’、‘}’，这里先不提栈的概念，我们想要检测后边的字符中是否含有与该左字符配对的右字符，就要先把这个左字符存起来，假设一个用例为 ‘([{}])’，这样把前一半 ‘([{’ 都存好后，要先把 ‘{’ 拿出来与后边的右字符相比较，而 ‘{’ 恰好是最后一个存放的左字符，这下思路应该清晰了，后存放的左字符要先取出来拿去比较，后进先出，这不是典型的栈嘛

发现这点后以此为中心设计解题方法，即每次遇到一个新的左字符，就将他压入栈中，遇到右字符，就检测他是否可以与当前的栈顶数据配对，如果可以，就将栈顶数据出栈，然后继续检查后续的字符。只要有没能匹配成功或者栈已经空了，就说明当前检测的字符串是非法的，反之用这个方法遍历了整个字符串后就说明字符串是合法的

代码

#define MAXSIZE 10240

typedef struct {
	char data[MAXSIZE];
	int top;
}SeqStack;

SeqStack *InitSeqStack() {
	SeqStack *s;
	s = (SeqStack*)malloc(sizeof(SeqStack));
	s->top = -1;
	return s;
}

int Push_SeqStack(SeqStack *s, char d) {
	if (s->top == MAXSIZE - 1)
		return 0;
	else {
		s->top++;
		s->data[s->top] = d;
		return 1;
	}
}


int Empty_SeqStack(SeqStack *s) {
	if (s->top == -1)
		return 1;
	else
		return 0;
}

int Pop_SeqStack(SeqStack *s) {
	if (Empty_SeqStack(s))
		return 0;
	else { 
		s->top--;
		return 2;
	}
}

class Solution {
public:
    SeqStack *stack;
    bool isValid(string s) {
        int i;
        char now;
        stack = InitSeqStack();
        for(i = 0; s[i]; i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                int a = Push_SeqStack(stack, s[i]);
                cout << a;
            }
            else {
                if (Empty_SeqStack(stack) == 1)
                    return false;
                else if (s[i] == ')')
                    now = '(';
                else if (s[i] == '}')
                    now = '{';
                else if (s[i] == ']')
                    now = '[';
                else {
                    now = 'a';
                }
                if(stack->data[stack->top] == now) {
                    int b = Pop_SeqStack(stack);
                    cout << b << endl; 
                    continue;
                }
                else
                    return false;
            }
        }
        if(Empty_SeqStack(stack) == 1)
            return true;
        else
            return false;
    }
};

经过何涛大佬指点后

傻吊的我并不知道要用封装好的栈，并把我的几个检测变量删掉了，内存消耗一下子就降下来啦，别人的代码就是不一样！

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