博客

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([)]”

输出：false

示例 5：

输入：s = “{[]}”

输出：true

思路：申请一个strlen(s)长度的空间来当做栈，把左括号的都入栈，当遇到右括号出栈比较，判断栈是否为空，如果为空，返回false,如果不为空，比较是否是相适应的括号，如果不是返回false.直到比较完括号，判断栈是否为空，为空返回true,否则返回false.

ASCII 码表中小括号的相差1，花括号和方括号相差2

代码：

bool isValid(char * s){
    char *flat=(char *)malloc(strlen(s));
    int i=0,k=0;
        while(s[i])
        {
            if(s[i]=='(' || s[i]=='{' ||s[i]=='[')
            {
                flat[k++]=s[i];
            }else if(--k>=0)
            {
                if(!( s[i]-2==flat[k] || s[i]-1==flat[k]))
                {
                    free(flat);
                    return false;
                }   
            }else
            {
                free(flat);
                return false;
            }
            i++;
        }
  

    free(flat);
    if(k==0)
        return true;
    else
        return false;
}