[数据结构与算法]leetcode每日一题—678.有效的括号字符串

题目：
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. *可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。
   
   思路：
   无效字符串举例：" ?( "
   用两个栈stack1和stack2分别来记录 ?和（的位置，以便后续判别 ?和（的相对位置，进而判断字符串是否有效。
   因为 ?可以用作三种字符，所以对）进行匹配时，优先使用(，其次使用?。如果两个栈都为空，则说明当前字符串无效。
   如果字符串遍历完毕时，如果：
   （1）（栈还有元素，?栈为空，则当前字符串无效；
   （2）（栈为空，?栈还有元素，则当前字符串有效；
   （3）如果两个栈都不为空，则需要对(栈中的元素挨个进行判断，看当前?栈中的位置索引 是否大于 （栈中的位置索引，如果小于则当前字符串无效，直接退出；否则判断下一个元素，直至（栈为空。

解答：

class Solution:
    def checkValidString(self, s: str) -> bool:
        sl=list(s)
        n=len(sl)
        #stack1记录*的位置
        #stack2记录(的位置
        stack1,stack2=[],[]
        ans=0
        for i in range(n):
            c=sl[i]
            if c=='*':
                stack1.append(i)
            elif c=='(':
                stack2.append(i)
            elif c==')':
                if stack2:
                    stack2.pop()
                elif stack1:
                    stack1.pop()
                else:
                    return False
        print(stack1,stack2)
        while stack2:
            #（的位置
            a=stack2.pop()
            if stack1:
                # *的位置
                b=stack1.pop()
            else:
                return False
            if a>b:
                return False
        return True