[LeetCode C 实现]20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

bool isValid(char* s) 
{
    int sLen=strlen(s);
    if(sLen%2!=0)
    {
        return false;
    }
    int *map=(int *)malloc(sizeof(int)*(sLen/2+1));
    int a[126]={0};
    a['(']=1;
    a['[']=1;
    a['{']=1;
    a[')']='(';
    a[']']='[';
    a['}']='{';
    int count=0;
    for(int i=0;i<sLen;i++)
    {
        if(a[s[i]]==1) 
        {
            map[count++]=s[i];
        }
        else
        {
            if(count!=0 && a[s[i]]==map[count-1])
            {
                count--;
            }
            else
            {
                return false;
            }
        }
        
        if(count>sLen/2)
        {
            return false;
        }
    }
    
    if(count!=0)
    {
        return false;
    }
    
    return true;
}

C语言中自己实现栈，相应的解决方案：

/*定义栈的初始大小*/
#define STACK_INITSIZE   100
/*定义增幅*/
#define STACK_INCREMENT  100
typedef int ElemType;

int realsize = STACK_INITSIZE;
/*顺序栈的实现*/
typedef struct SqStack
{
    /*指向申请的内存，用于存储栈数据结构*/
    ElemType *data;
    int top;
}SqStack;

/*栈的初始化*/
int initstack(SqStack * s)
{
    /*入参为NULL，返错*/
    if(NULL == s)
        return -1;
    s->top = -1;
    s->data = (ElemType *)malloc(STACK_INITSIZE * sizeof(ElemType));
    /*申请内存失败，返错*/
    if(NULL == s->data)
        return -1;
    
    return 0;
}

/*判断栈空*/
bool stackempty(SqStack *s)
{
    if(NULL == s)
        return true;
    
    if(-1 == s->top)
        return true;
    else
        return false;
}

/*入栈操作*/
int push(SqStack *s,ElemType x)
{
    if(NULL == s)
        return -1;
    
    /*栈满，再分配STACK_INCREMENT个元素*/
    if(realsize-1 == s->top)
    {
        realsize += STACK_INCREMENT;
        s->data = (ElemType *)realloc(s->data,realsize*sizeof(ElemType));
        /*申请内存失败，返错*/
        if(NULL == s->data)
            return -1;
    }
    
    s->top += 1;
    s->data[s->top] = x;
    
    return 0;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
    if(NULL == s)
        return false;
    
    if(stackempty(s))
        return -1;
    
    *x = s->data[s->top];
    s->top--;
    return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
    if(stackempty(s))
        return -1;
    *x = s->data[s->top];
    return *x;
}
/*清空栈,只是将top设置为-1,没有释放申请的内存*/
void clearstack(SqStack *s)
{
    if(stackempty(s))
        return;
    s->top = -1;
}
void destorystack(SqStack *s)
{
    if(NULL == s)
        return;
    
    if(s->data != NULL)
        free(s->data);
    s->top = -1;
}

bool isValid(char* s) 
{
    /*申请栈*/
    SqStack stack;
    initstack(&stack);
    
    int ele = 0;
    int len = strlen(s);
    if(len%2!=0)
    {
        return false;
    }
    for(int i=0;i<len;i++)
    {
        if(s[i]=='(' || s[i]=='[' ||s[i]=='{')
        {
            push(&stack,s[i]);
        }
        else if(s[i]==')')
        {
            if(gettop(&stack,&ele) != '(')
                return false;
            else
                pop(&stack,&ele);
        }
        else if(s[i]==']')
        {
            if(gettop(&stack,&ele) != '[')
                return false;
            else
                pop(&stack,&ele);
        }
        else if(s[i]=='}')
        {
            if(gettop(&stack,&ele) != '{')
                return false;
            else
                pop(&stack,&ele);
        }
        else
        {
            return false;
        }
            
    }

    int ret = stackempty(&stack);
    destorystack(&stack);
    return ret;
}

相应的栈实现参考之前文章中的实现：栈操作C语言实现
C++实现方法一：

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

C++实现，更简洁、高效的方法(击败100%）：

class Solution {
public:
    bool isValid(string s) {        
        stack<char> bstack;
        for(const auto &c:s)
        {
            switch(c)
            {
                case '{':bstack.push('}');break;
                case '[':bstack.push(']');break;
                case '(':bstack.push(')');break;
                default:
                    if(bstack.empty() || (c != bstack.top())) return false;
                    else
                        bstack.pop();
            }
        }
        
        return bstack.empty();
    }
};

运行结果：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
Memory Usage: 6.4 MB, less than 36.61% of C++ online submissions for Valid Parentheses.

C++比较高效的一种实现方式:

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> st;
        for(int i = 0;i < s.size();i++)
        {
            if(s[i] == '(' || s[i]=='{' || s[i] =='[')
                st.push(s[i]);
            else {
                //寻找左括号,st为空非法
                if(st.empty()) return false;
                char ch = st.top();
                if(s[i] == ')' && ch != '(' ||
                   s[i] == '}' && ch != '{' ||
                   s[i] == ']' && ch != '[')
                   return false;

                st.pop();
            }
        }
        if(st.size()) return false;

        return true;
    }
};

运行结果：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了81.75%的用户
通过测试用例：
91 / 91

另一种代码看起来非常简洁，性能却略逊一筹的解法：

class Solution {
public:
    bool isValid(string s) {
        int size = s.size();
        if(size % 2) return false;

        std::stack<char> st;
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for(int i = 0;i < size;i++)
        {
            if(pairs.count(s[i]))
            {
                if(st.empty() || st.top() != pairs[s[i]])
                    return false;
                st.pop();
            }else{
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};

52coder

[LeetCode C 实现]20. Valid Parentheses