0020. Valid Parentheses

题目分析：只有()[]{}六种字符，那么可以考虑遇到左括号压到栈里，遇到右括号则从栈里弹出一个比较。
如果遇到右括号而栈已空，则匹配失败。
所以字符比较完，如果匹配，则栈必然为空，否则匹配失败。

• C语言版本
  Runtime: 4 ms, faster than 26.71% of C online submissions for Valid Parentheses.
  Memory Usage: 7.2 MB, less than 100.00% of C online submissions for Valid Parentheses.

typedef struct _listnode{
    char ch;
    struct _listnode* next;
}ListNode;

ListNode* init(){
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    return head;
}

void push(ListNode* head, char ch){
    ListNode* nd = (ListNode*)malloc(sizeof(ListNode));
    nd->ch = ch;
    nd->next = head->next;
    head->next = nd;
}

char pop(ListNode* head){
    ListNode* trgt = head->next;
    if(trgt==NULL)
        return ' ';
    char ch = trgt->ch;
    head->next = trgt->next;
    free(trgt);
    trgt = NULL;
    return ch;
}

int empty(ListNode* head){
    if(head->next==NULL)
        return 1;
    else
        return 0;
}

bool isValid(char* s) {
    ListNode* stk = init();
    int i=0;
    char c;
    char lc;
    while((c=s[i])!='\0'){
        if(c=='(' || c=='[' || c=='{'){
            push(stk,c);
        }else{
            if(empty(stk) == 1)
                return 0;
            lc = pop(stk);
            if(lc=='(' && c!=')')
                return 0;
            if(lc=='[' && c!=']')
                return 0;
            if(lc=='{' && c!='}')
                return 0;
        }
        i++;
    }
    return empty(stk);
}

• Java的第一个版本
  Runtime: 4 ms, faster than 98.31% of Java online submissions for Valid Parentheses.
  Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Valid Parentheses.

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk = new Stack<Character>();
        int i=0;
        int len = s.length();
        char c;
        char lc;
        while(i<len){
            c = s.charAt(i);
            i++;
            if(c=='(' || c=='[' || c=='{'){
                stk.push(c);
            }else{
                if(stk.empty()==true)
                    return false;
                lc = stk.pop();
                if(lc=='(' && c!=')')
                    return false;
                if(lc=='[' && c!=']')
                    return false;
                if(lc=='{' && c!='}')
                    return false;
            }
        }
        return stk.empty();
    }
}

• Java的另一个版本，比较Java

public class Solution {
    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
            if (c == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            }
            if (c == '}') {
                if (stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}