深圳市住房和建设网站北京网校

LeetCode | 20. 有效的括号

OJ链接

• 这道题可以使用栈来解决问题~~

思路：

• 首先我们要使用我们之前写的栈的实现来解决此问题~~
• 如果左括号，就入栈
• 如果右括号，出栈顶的左括号跟右括号判断是否匹配
  • 如果匹配，继续
  • 如果不匹配，终止

代码如下：

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;//top 表示指向栈顶元素//ps->top = -1;//top 表示指向栈顶元素的下一个ps->top = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("relloc fail!\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
// 出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
// 获取栈顶元素
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;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
// 销毁栈
void StackDestroy(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}bool isValid(char* s) {ST st;StackInit(&st);while(*s){switch(*s){case ')':case ']':case '}':{if(StackEmpty(&st)){StackDestroy(&st);return false;}char top = StackTop(&st);StackPop(&st);if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){StackDestroy(&st);return false;}else{++s;}break;}case '(':case '[':case '{':{StackPush(&st,*s);++s;break;}default:break;}}bool ret = StackEmpty(&st);StackDestroy(&st);return ret;
}