当前位置: 首页> 娱乐> 影视 > 哈尔滨小程序制作公司_seo网站推广优化论文_扬州seo博客_外链下载

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

时间:2025/7/9 8:16:29来源:https://blog.csdn.net/2401_87255690/article/details/145835044 浏览次数:0次
哈尔滨小程序制作公司_seo网站推广优化论文_扬州seo博客_外链下载

题目如下:

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

bool isValid(char* s) {}

解题过程如下:

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

  1. 思路中提到了“借助数据结构栈”,那么就可以把之前学的栈的实现放在已知代码前面了:
//定义栈的结构
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) {}
  1. 养成初始化和销毁一起写的好习惯,本题代码的具体内容写在初始化和销毁代码之间:

在这里插入图片描述

  1. return true;return false;代码之前先销毁栈。
  2. 根据前面的分析,得到的代码如下:
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. 以上代码会有报错的风险,一般看执行到哪一步有问题就在哪一步之前改进代码,看看以下示例,完善代码:

示例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;
}
关键字:哈尔滨小程序制作公司_seo网站推广优化论文_扬州seo博客_外链下载

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: