08 - 请帮我测试字符串
本帖最后由 鱼C-小师妹 于 2021-5-14 19:01 编辑https://www.bilibili.com/video/BV1HT4y1K7DY?p=10
学习完上面的条件结构和循环结构，相信很多童鞋都和小由鱼一样都认为学编程没那么难啦～
这不小由鱼的女神又来向他求助，又到了他大展拳脚的时候咯：
小由鱼鸽鸽，遇到个棘手问题，救救孩子吧，老师留作业要写个程序判断给定的字符串 s 中括号的写法是否合法。
下面是约束条件：
[*]字符串仅包含 '('、')'、'['、']'、'{'、'}' 这三对括号的组合
[*]左右括号必须成对编写，比如 "()" 是合法的，"(" 则是非法的
[*]左右括号必须以正确的顺序闭合，比如 "{()}" 是合法的，"{(})" 则是非法的
示例：
看完题目，因为学了前几讲，小由鱼很是淡定，女神这个忙，自己肯定能帮上！
不过动手实现前，还是要整理下思路！
明显这个问题就是解决括号匹配问题！
需要额外使用一个“特殊”的列表来作为临时存储。
这个列表之所以特殊，是因为我们需要：
[*]从前往后填入数据
[*]从后往前提取数据
“从前往后填入数据”这是正常行为，append() 方法即可实现；
”从后往前提取数据”听着新鲜，remove() 方法不行。
呃..
对，pop() 方法可以！
遍历给定的字符串 s 时，当遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。
比如 "[]" 这样。
但是，如果遇到的场景是类似 "[()]" 这种括号嵌套，也就是连续出现多个左括号，那么先出现的那个就不能急着去匹配，需要等待后面的匹配完，再轮到它。
比如 "[()]"，是不是得先匹配内部的 "()"，然后再匹配外部的 "[]"。
这时候，就要用到那个特殊列表。
当遇到左括号的时候，不管 3721，把它塞到特殊列表中：
当遇到右括号的时候，不管 7749，再特殊列表的末尾提取一个元素进行匹配。
比如 "[()]"，第三个元素是 ')'，从特殊列表的尾部提取出 '('，匹配成功，放行……
继续下一个 ']'，此时特殊列表只剩下 '['，匹配成功，遂打印 “合法^o^”。
思路到此就很清楚啦！
从上面的思路分析，我们可以知道程序肯定要用到：循环。
而循环中需要用到 break 语句，在 07 最后我们说过：
循环中如果有 continue 或 break 语句，那么就无法写成盒图。
通过上面的分析除了用到循环，还要用到多条件分支结构，那毫无疑问画成流程图最方便：
流程图中会用到的 while...else... 结构相信你们懂哈。
小甲鱼老师有讲过，不懂请看最新版 P17 讲：
https://www.bilibili.com/video/av52080698?p=18
简单说就是：
在 for 循环完整完成后才执行 else；
如果中途从 break 跳出，则连 else 一起跳出。
好啦，流程图有了，将其翻译成代码：
**** Hidden Message *****
搞定，测试下没问题！
善于观察的鱼油应该察觉到了，变量叫 “Stack”！
没错，上面的结构，就是“栈”，先记住，以后会很有用哦～
好啦，下课～ 这题目一点都不简单 wp231957 发表于 2021-4-23 18:32
这题目一点都不简单
我想到了之前的作业有一题是栈 快讲快讲，当时就卡在这道题目 有点难
厉害 1 瞎搞版：
def KuoHao(a, b, c, d):
if c < d:
if temp.find(a, c, d) == -1:
if temp.find(b, c, d) != -1:
return 1
elif temp.find(b, c, d) == -1:
return 1
elif (temp.find(a, c, d) - temp.find(b, c, d)) % 2 == 0:
return 1
return KuoHao(a, b, temp.find(a, c, d) + 1, temp.find(b, c, d))
else:
return 0
temp = input('请输入测试字符串：')
li = list('()[]{}')
K = []
for i in range(0, 6, 2):
K.append(KuoHao(li, li, 0, len(temp)))
print('非法') if 1 in K else print('合法')
看了思路：
Str = input('请输入测试字符串：')
dictKH = {')': '(', ']': '[', '}': '{'}
LKH = ['(', '[', '{']
RKH = [')', ']', '}']
S = []
for i in Str:
if i in LKH:
S.append(i)
elif i in RKH:
if len(S) == 0 or S.pop() != dictKH:
print('非法')
break
else:
print('合法')
{:10_245:} {:7_131:} 看看看看看看 我错了 s = "[]"
l = list(s)
l1 = ['{', '[', '(', ')', ']', '}']
l3 = []
for a in l:
for i in l1:
if a == i:
l3.append(l1.index(i))
for i in range(len(l3)):
if l3 + l3 == 5 and sorted(l3) == l3 and len(l3) % 2 == 0:
print("right")
break
else:
print("wrong")
break 看看代码 催更
来看看python的栈有没有c++的栈的实现那么麻烦
wp231957 发表于 2021-4-23 18:32
这题目一点都不简单
你去看看用c语言的栈实现这个括号匹配算法就知道什么叫做难了 1 代码
z = input("请输入测试字符串：")
s = set(z)
c = {'(',')','[',']','{','}'}
if s.issubset(c):
if (z.count('(') == z.count(')')) and (z.count('[') == z.count(']')) and (z.count('{') == z.count('}')):
if ((z.index('(') + z.index(')')) % 2 != 0) or ((z.index('[') + z.index(']')) % 2 != 0) ((z.index('{') + z.index('}')) % 2 != 0):
print('合法')
else:
print("非法")
else:
print("非法")
else:
print("非法")
我写的好复杂啊！！！