首页 > 其他分享 >Problem J: 括号匹配问题

Problem J: 括号匹配问题

时间:2023-04-28 19:34:50浏览次数:41  
标签:__ 匹配 self 括号 Problem line def

Problem Description

在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。

Input Description

输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。 注意:cin.getline(str,100)最多只能输入99个字符!

Output Description

对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。

Sample Input

bge)))))))))
((IIII))))))
()()()()(uuu
))))UUUU((()

Sample Output

bge)))))))))
   ?????????
((IIII))))))
        ????
()()()()(uuu
        $   
))))UUUU((()
????    $$  

Hint

 算法思想:

括号匹配是典型的栈的应用,因此可以采用链栈,思路如下: (1)第一次遍历输入字符串,         1.是左括号,则入栈,同时标记数组的相应位置置空格         2.是右括号,则检测栈是否为空,不为空,则判断有对应的左括号,同时出栈;为空,则没有对应的左括号,标记数组置‘?’ (2)第二次遍历输入字符串,         1.是右括号,则入栈。         2.是左括号,则检测栈是否为空,不为空,则判断有对应的右括号,同时出栈;为空,则没有对应的左括号,标记数组置‘$’。   ac代码:
 1 # 本题易错,List是可变的,传到函数里是指针,所以赋值给新的变量保存也会修改它本身的值,只能拷贝保存
 2 # 找左括号无法匹配要逆转列表看入栈的顺序
 3 # 顺序存储
 4 class Stack(object):
 5     # 初始化一个栈
 6     def __init__(self, size=100):
 7         self.stack = []
 8         self.size = size
 9         self.top = -1
10 
11     # 判断堆栈是否为空
12     def isEmpty(self):
13         return self.top == -1
14 
15     # 判断栈是否已满
16     def is_full(self):
17         return self.top + 1 == self.size
18 
19     # 入栈操作
20     def pushStack(self, val):
21         if self.is_full():
22             raise Exception("Stack is full")
23         else:
24             self.top += 1
25             self.stack.append(val)
26 
27     # 出栈操作
28     def popStack(self):
29         if self.isEmpty():
30             raise Exception("Stack is empty")
31         else:
32             self.top -= 1
33             self.stack.pop()
34 
35 def func():
36     while True:
37         try:
38             x = []
39             x = input()
40             x = list(x)
41             Match(x)
42         except EOFError:
43             break
44 def Match(line):
45     t = []
46     t = line.copy()
47     print(''.join(t))
48     # 实例化一个栈
49     s = Stack()
50     j = 0
51     # 找右括号是否匹配
52     for i in line:
53         t[j] = ' '
54         if i=='(':
55             s.pushStack(i)
56         if i==')':
57             if s.isEmpty():
58                 t[j] = '?'
59             else:
60                 s.popStack()
61         j += 1
62     # 找左括号是否匹配,注意不能拆开比较,括号有左右之分
63     w = Stack()
64     flag = 0
65     length = len(line)
66     j = 0
67     m = line[::-1]
68     for i in m:
69         if i == ')':
70             w.pushStack(i)
71         if i == '(':
72             if w.isEmpty():
73                 t[length-1-j] = '$'
74             else:
75                 w.popStack()
76         j += 1
77     print(''.join(t))
78 if __name__ == '__main__':
79     func()

 

标签:__,匹配,self,括号,Problem,line,def
From: https://www.cnblogs.com/hangsingplus/p/17362986.html

相关文章

  • NC50454 A Simple Problem with Integers
    题目链接题目题目描述给定数列\(a[1],a[2],\dots,a[n]\),你需要依次进行q个操作,操作有两类:1lrx:给定l,r,x,对于所有\(i\in[l,r]\),将a[i]加上x(换言之,将\(a[l],a[l+1],\dots,a[r]\)分别加上x);2lr:给定l,r,求\(\sum_{i=l}^ra[i]\)的值(换言之,求\(a[l]+a[l+1]+\dots+a......
  • 6669: 括号配对 区间dp
    描述 Hecy又接了个新任务:BE处理。BE中有一类被称为GBE。以下是GBE的定义:空表达式是GBE如果表达式A是GBE,则[A]与(A)都是GBE如果A与B都是GBE,那么AB是GBE。 输入 输入仅一行,为字符串BE。对于100%的数据,输入的字符串长度小于100。 输......
  • NC51100 A Simple Problem with Integers
    题目链接题目题目描述YouhaveNintegers,\(A_1,A_2,...,A_N\).Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagivenint......
  • CF1699A The Third Three Number Problem
    题意简述构造出一个三元组a,b,c使得(a⊕b)+(a⊕c)+(b⊕c)=n,若无解输出-1。符号⊕的意思为异或个人分析首先要了解异或符号的性质:1,x⊕0=x2,x⊕x=x根据异或符号的性质可以得到一下构造:a=b=0,c=n/2c=0,a=b=n/2通过上述可以发现答案都是偶数所以若n为奇则无解......
  • Rust -- 模式与匹配
    1.模式用来匹配类型中的结构(数据的形状),结合模式和match表达式提供程序控制流的支配权模式组成内容字面量解构的数组、枚举、结构体、元祖变量通配符占位符流程:匹配值-->是否拥有正确的数据-->运行特定的代码2.使用模式的位置match分支:由match关键字、......
  • 「CF1188E」Problem from Red Panda
    题目点这里看题目。给定一个长度为\(k\)的非负整数序列\(a\)。你可以对于\(a\)做如下操作任意次:选定\(1\lej\lek\),满足除了\(a_j\)外\(a\)中其它数都为正。而后,令\(a_j\)加上\(k-1\),令除了\(a_j\)外\(a\)中其它数减去\(-1\)。(这样一次操作被称为“操......
  • poj 2584 T-Shirt Gumbo 二分匹配
    T-ShirtGumboTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 2935 Accepted: 1376DescriptionBoudreauxandThibodeauxarestudentvolunteersforthisyear'sACMSouthCentralRegion'sprogrammingcontest.Oneoftheirdutiesis......
  • FZU Problem 1894 志愿者选拔 单调队列
    题目:http://acm.fzu.edu.cn/problem.php?pid=1894题意:ProblemDescription世博会马上就要开幕了,福州大学组织了一次志愿者选拔活动。参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。面试......
  • 基于ICP配准算法的三维点云数据的匹配仿真
    1.算法仿真效果matlab2022a仿真结果如下:       2.算法涉及理论知识概要       ICP算法能够使不同的坐标下的点云数据合并到同一个坐标系统中,首先是找到一个可用的变换,配准操作实际是要找到从坐标系1到坐标系2的一个刚性变换。ICP算法本质上是基于最小......
  • PCRE库某种情况下如果匹配慢
    如果被匹配的内容超过几十兆字节,pcre2_match()中的倒数第三个参数选用:0 ,就会很慢,如果匹配次数多,就会非常慢。我用一个20兆的文件,匹配90000多个电话号,一天时间都没有匹配结束。但是这个参数如果用了  PCRE2_NO_UTF_CHECK  ,秒完......