#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//struct Stack
//{
//  int a[N];
//  int top; // 栈顶的位置
//};
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 栈顶的位置
  int capacity; // 容量
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDataType StackTop(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    ps->a = (STDataType*)realloc(ps->a, newCapacity* sizeof(STDataType));
    if (ps->a == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  --ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  /*if (ps->top > 0)
  {
    return false;
  }
  else
  {
    return true;
  }*/
  return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if((*s=='(')||(*s=='[')||(*s=='{'))
        {
            //左括号就入栈   右括号就出栈
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //如果需要出栈 但是已经没有可出的了，说明不匹配直接return
            //如： ()) 
            if(StackEmpty(&st))
            return false;
            //取栈顶
            char top=StackTop(&st);
            StackPop(&st);
            //因为继续的条件有很多，所以我们判断return的条件
            //这里很值得注意
            if((*s==')' && top!='(')
            ||(*s==']' && top!='[')
            ||(*s=='}' && top!='{'))
            {
                StackDestory(&st);
                return false;
            }
            s++;
        }
    }
    //如果栈此时不等于空，就说明左括号有多余的
    if(!StackEmpty(&st))
    {
        StackDestory(&st);
        return false;
    }
    //此时栈为空，说明前面的左右括号都匹配了
    else
    {
        StackDestory(&st);
        return true;
    }
}