顿搜
飞过闲红千叶，夕岸在哪
类目归类
栈——算法设计 · 篇六
08/15
一、判断括号是否匹配
GitHub地址：判断括号是否匹配，栈的反转.cpp
- ①、判断一个括号字符串组成的序列是否合法
1、开始借助栈这个数据结构的特性来遍历整个字符串
- ②、使用递归的方法将栈中的数据进行翻转*
1、取出栈顶元素，递归调用，翻转剩余的元素
2、将取出的元素放入栈底部
3、压栈时，如果栈为空，那么直接将元素放到栈的底部即可
4、如果栈中有元素，那么取出栈中的元素，将原来的元素再次调用函数存放到栈底，然后将取出的元素压入栈
二、求解后缀表达式
GitHub地址：求解后缀表达式.cpp
1、如果当前的字符串为符号，需要从栈中取出操作数
2、计算后将结果压入到栈中。
3、 其他情况都只需要将当前字符串压入栈内即可
三、简化目录路径
GitHub地址：简化目录路径.cpp
- ①、一个表达式所表述的路径，进行最简化
对于 ./ ../ 和 / 分类讨论，分别进行处理即可
四、最长合法括号匹配长度
GitHub地址：最长合法括号匹配长度.cpp
- ①、最长合法括号匹配长度
1、使用一个bool数组来标记已经匹配过的字符
2、直到最长的连续标记的长度就是所求的结果，只需要两次遍历数组，时间复杂度为O(n)
法二
1、使用栈记录某一个符号在字符串中的位置
2、假如对于当前字符和栈顶位置的字符可以匹配，
3、那么可以根据栈是否为空来判断当前最长匹配子序列然后和目标进行匹配
