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


The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

C

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

struct node  
{  
    char data;  
    struct node* down;  
};  
typedef struct node node;

struct stack
{
    node* top;
    int size;
};
typedef struct stack Stack;

Stack* EmptyStack()
{
    Stack *top = (Stack*)malloc(sizeof(Stack*));
    if(top)
    {
        top->top = NULL;
        top->size = 0;
    }   
    return top;
}

int IsEmpty(Stack* stack)
{
    if(!stack->top && stack->size == 0) return 1;
    return 0;
}
 
node* push(Stack* stack,char element)
{
    node* newtop = (node*)malloc(sizeof(node*));
    newtop->data = http://www.mamicode.com/element;>


C++
class Solution {
public:
    bool isValid(string s) {
        stack<char> charstack;    
        string::iterator it = s.begin();
        while(it != s.end()) {
            if(*it=='{' || *it=='[' || *it=='(') charstack.push(*it);
            else if (*it=='}'){
                if(!charstack.empty() && charstack.top()=='{') charstack.pop();
                else return false;
            }
            else if (*it==']'){
                if(!charstack.empty() && charstack.top()=='[') charstack.pop();
                else return false;
            }
            else if (*it==')'){
                if(!charstack.empty() && charstack.top()=='(') charstack.pop();
                else return false;
            }
            else return false;
            it++;
        }  
        if(charstack.empty()) return true;
        else return false;
    }
};


Valid Parentheses