给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围:
"()()"
true
"((*)"
true
"(*)"
true
"(((*)"
false
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here star_stack = [] symbol_stack = [] for i in range(len(s)): if s[i:i+1] == '(': symbol_stack.append([i,'(']) elif s[i:i+1] == '*': star_stack.append([i,'*']) else: if symbol_stack: symbol_stack.pop() continue elif len(symbol_stack) == 0 and star_stack: star_stack.pop() continue else: return False while symbol_stack: if len(star_stack) == 0: return False if symbol_stack.pop()[0] > star_stack.pop()[0]: return False return True
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here #定义2个空栈,一个用来存放左括号,一个用来存放*号,遇到右括号的时候先出stack1,当stack1为空的时候,再出stack2,当stack2为空的时候,返回False #print("ok") stack1=[] stack2=[] #print(s) for x in range(len(s)): if s[x] == "(": stack1.append(x) elif s[x]=="*": stack2.append(x) elif s[x]==")": if len(stack1)>0: stack1.pop() elif len(stack2)>0: stack2.pop() else: return False print(stack1) print(stack2) #如果比较完,stack1等于0的话,说明括号已经完全匹配了,返回true即可 if len(stack1) ==0: return True #如果说stack1大于0,并stack2大于0.stack1的元素比stack2多,需要比较stack1中的括号的位置与*的索引顺序,小于*Hao的索引才能匹配,大于星号则永远不能匹配,当stack1中的元素pop完退出while循环或者当stack1中的元素的pop值比stack2还大,需要将pop出的元素append回来直接break出循环体,最后通过比较stack1中的元素数量如果为空了,就匹配成功了说明,否则匹配失败 elif len(stack1)>0 and len(stack2)>0 and len(stack1)<=len(stack2) : while len(stack1)>0 : x=int(stack1.pop()) y=int(stack2.pop()) print(stack1,x,y) if x<y: pass else: stack1.append(x) break print(stack1) if len(stack1) ==0: return True else: return False else: return False
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValidString(self , s: str) -> bool: # write code here left = [] star =[] s = s[1:-1] # 把所有(和*当左边界压入栈 for i in range(len(s)): if s[i] == '(': left.append(i) elif s[i] == '*': star.append(i) else: # )右括号出栈 if len(left): left.pop() elif len(star): star.pop() # 右括号不够匹配了,返回false else: return "false" # 然后右括号匹配 while len(left) and len(star): if len(left)>len(star): return "false" if left.pop() > star.pop(): return "false" return "true" print(Solution().isValidString(input()))翻译过来的为啥输出不通过