08 - 请帮我测试字符串

鱼C-小师妹

学习完上面的条件结构和循环结构，相信很多童鞋都和小由鱼一样都认为学编程没那么难啦～

这不小由鱼的女神又来向他求助，又到了他大展拳脚的时候咯：

小由鱼鸽鸽，遇到个棘手问题，救救孩子吧，老师留作业要写个程序判断给定的字符串 s 中括号的写法是否合法。

下面是约束条件：

• 字符串仅包含 '('、')'、'['、']'、'{'、'}' 这三对括号的组合
• 左右括号必须成对编写，比如 "()" 是合法的，"(" 则是非法的
• 左右括号必须以正确的顺序闭合，比如 "{()}" 是合法的，"{(})" 则是非法的
  

示例：



看完题目，因为学了前几讲，小由鱼很是淡定，女神这个忙，自己肯定能帮上！

不过动手实现前，还是要整理下思路！

明显这个问题就是解决括号匹配问题！

需要额外使用一个“特殊”的列表来作为临时存储。

这个列表之所以特殊，是因为我们需要：

• 从前往后填入数据
• 从后往前提取数据
  

“从前往后填入数据”这是正常行为，append() 方法即可实现；

”从后往前提取数据”听着新鲜，remove() 方法不行。

呃..

对，pop() 方法可以！

遍历给定的字符串 s 时，当遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。

比如 "[]" 这样。

但是，如果遇到的场景是类似 "[()]" 这种括号嵌套，也就是连续出现多个左括号，那么先出现的那个就不能急着去匹配，需要等待后面的匹配完，再轮到它。

比如 "[()]"，是不是得先匹配内部的 "()"，然后再匹配外部的 "[]"。

这时候，就要用到那个特殊列表。

当遇到左括号的时候，不管 3721，把它塞到特殊列表中：



当遇到右括号的时候，不管 7749，再特殊列表的末尾提取一个元素进行匹配。

比如 "[()]"，第三个元素是 ')'，从特殊列表的尾部提取出 '('，匹配成功，放行……

继续下一个 ']'，此时特殊列表只剩下 '['，匹配成功，遂打印 “合法^o^”。

思路到此就很清楚啦！

从上面的思路分析，我们可以知道程序肯定要用到：循环。

而循环中需要用到 break 语句，在 07 最后我们说过：

循环中如果有 continue 或 break 语句，那么就无法写成盒图。

通过上面的分析除了用到循环，还要用到多条件分支结构，那毫无疑问画成流程图最方便：



流程图中会用到的 while...else... 结构相信你们懂哈。

小甲鱼老师有讲过，不懂请看最新版 P17 讲：



简单说就是：

在 for 循环完整完成后才执行 else；

如果中途从 break 跳出，则连 else 一起跳出。

好啦，流程图有了，将其翻译成代码：

游客，如果您要查看本帖隐藏内容请回复

搞定，测试下没问题！

善于观察的鱼油应该察觉到了，变量叫 “Stack”！

没错，上面的结构，就是“栈”，先记住，以后会很有用哦～

好啦，下课～

wp231957

这题目一点都不简单

柿子饼同学

wp231957 发表于 2021-4-23 18:32
这题目一点都不简单

我想到了之前的作业有一题是栈

bool想学C

快讲快讲，当时就卡在这道题目

张大帅

有点难

felix_zwl

厉害

calrai11

1

zhangyuesd

瞎搞版：
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[i], li[i + 1], 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[i]:
            print('非法')
            break
else:
    print('合法')
        

yangtao120

天天今天要健身

旗鱼骑士的旗鱼

看看看看看看

深邃海绵

我错了

liuyiming1989

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[i] + l3[len(l3)-i-1] == 5 and sorted(l3) == l3 and len(l3) % 2 == 0:
        print("right")
        break
    else:
        print("wrong")
        break

末世泽

看看代码

python357159

催更

python萌新258

来看看python的栈有没有c++的栈的实现那么麻烦

python萌新258

wp231957 发表于 2021-4-23 18:32
这题目一点都不简单

你去看看用c语言的栈实现这个括号匹配算法就知道什么叫做难了

listenc

1

LyyLD

代码

游刃鱿鱼

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("非法")

我写的好复杂啊！！！