哈尔滨小程序制作公司_seo网站推广优化论文_扬州seo博客_外链下载

题目如下：

有效的括号
在这里插入图片描述
已知代码：

bool isValid(char* s) {}

解题过程如下：

思路：借助数据结构—栈。遍历字符串，遇到左括号则入栈，遇到右括号则与栈顶元素比较，判断是否相匹配。若匹配，则栈中的栈顶元素出栈。最后，保证栈为空则为有效的字符串。

思路中提到了“借助数据结构栈”，那么就可以把之前学的栈的实现放在已知代码前面了：

//定义栈的结构
typedef char STDataType;//这回是char类型的数据
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置int capacity;//容量
}ST;
//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}
//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{assert(ps);//空间不够，扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈---栈顶
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
//获取栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}bool isValid(char* s) {}

养成初始化和销毁一起写的好习惯，本题代码的具体内容写在初始化和销毁代码之间：

在这里插入图片描述

在return true;或return false;代码之前先销毁栈。
根据前面的分析，得到的代码如下：

bool isValid(char* s) {ST st;STInit(&st);//遍历已知的字符串schar* pi = s;while (*pi != '\0')//当没有遍历到字符串的末尾时进入循环{//若遍历到左括号，则进栈if (*pi == '(' || *pi == '[' || *pi == '{'){StackPush(&st, *pi);}//反之，若遍历到右括号，则与栈顶元素比较，判断是否匹配else{//取栈顶元素char top = StackTop(&st);//不匹配if ((top == '(' && *pi != ')')||  (top == '[' && *pi != ']')||  (top == '{' && *pi != '}')){STDestroy(&st);return false;}//匹配，则出栈StackPop(&st);}++pi;}STDestroy(&st);return true;
}

以上代码会有报错的风险，一般看执行到哪一步有问题就在哪一步之前改进代码，看看以下示例，完善代码：

示例1：

在这里插入图片描述

第一个字符就是右括号，应取栈顶元素比较，但是栈中没有元素可以比较，即栈为空，执行到代码char top = StackTop(&st);处会报错。改进方法就是在代码char top = StackTop(&st);前加上：

//当栈为空，则直接返回false
if (StackEmpty(&st))
{
STDestroy(&st);
return false;
}

示例2：

在这里插入图片描述

按照上述代码执行程序，当pi遍历到字符串末尾'\0'时，跳出循环，直接销毁栈、return true;，这个结果很明显是不对的，这是一个无效字符串。而且，这是栈为非空的状态，肯定不是有效的字符串。

在这里插入图片描述
改进方法就是在销毁代码前加上：

//如果栈为空，则所有的左括号都已经匹配完了，反之，就不是有效的字符串
bool ret = StackEmpty(&st) ? true : false;

综上，主要代码如下：

bool isValid(char* s) {ST st;STInit(&st);//遍历已知的字符串schar* pi = s;while (*pi != '\0')//当没有遍历到字符串的末尾时进入循环{//若遍历到左括号，则进栈if (*pi == '(' || *pi == '[' || *pi == '{'){StackPush(&st, *pi);}//若遍历到右括号。当栈为空，则直接返回false；反之，则与栈顶元素比较，判断是否匹配else{//当栈为空，则直接返回falseif (StackEmpty(&st)){STDestroy(&st);return false;}char top = StackTop(&st);//不匹配if ((top == '(' && *pi != ')')||  (top == '[' && *pi != ']')||  (top == '{' && *pi != '}')){STDestroy(&st);return false;}//匹配，则出栈StackPop(&st);}++pi;}//如果栈为空，则所有的左括号都已经匹配完了，反之，就不是有效的字符串bool ret = StackEmpty(&st) ? true : false;STDestroy(&st);return ret;
}

完整代码如下：

/*栈的实现*/
//定义栈的结构
typedef char STDataType;//这回是char类型的数据
typedef struct Stack
{STDataType* arr;int top;//指向栈顶的位置int capacity;//容量
}ST;
//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}
//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{assert(ps);//空间不够，扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈---栈顶
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
//获取栈中有效数据个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}bool isValid(char* s) {ST st;STInit(&st);//遍历已知的字符串schar* pi = s;while (*pi != '\0')//当没有遍历到字符串的末尾时进入循环{//若遍历到左括号，则进栈if (*pi == '(' || *pi == '[' || *pi == '{'){StackPush(&st, *pi);}//若遍历到右括号。当栈为空，则直接返回false；反之，则与栈顶元素比较，判断是否匹配else{//当栈为空，则直接返回falseif (StackEmpty(&st)){STDestroy(&st);return false;}char top = StackTop(&st);//不匹配if ((top == '(' && *pi != ')')||  (top == '[' && *pi != ']')||  (top == '{' && *pi != '}')){STDestroy(&st);return false;}//匹配，则出栈StackPop(&st);}++pi;}//如果栈为空，则所有的左括号都已经匹配完了，反之，就不是有效的字符串bool ret = StackEmpty(&st) ? true : false;STDestroy(&st);return ret;
}