1、题目

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

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

• 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  一个空字符串也被视为有效字符串。

链接：https://leetcode-cn.com/problems/valid-parenthesis-string
 

2、思路分析

1）双栈

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left, star; // 栈中保存下标
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '('){
                left.push(i);
            }
            else if(s[i] == '*'){
                star.push(i);
            }
            else { // 先出栈left中的左括号，在出栈*
                if(left.empty() && star.empty()) return false;
                if(!left.empty()) left.pop();
                else star.pop();
            }
        }
        while(!left.empty() && !star.empty()){
            if(left.top() > star.top()) return false; // 如果left的下标大于*的下标，那么就直接返回false
            left.pop();
            star.pop();
        }
        return left.empty();
    }
};