How to solve a problem about balancing parentheses with smileys?
The problem confused me as well until I understood that smileys can be separated into a colon and a parentheses if required (because a colon as the text says is also a valid character.) Now you can write a linear algorithm. By counting how many brackets are open, how many could be opened by smileys and how many could be closed by smileys:
int main() {
    int n; string s; 
    getline(cin,s); n = stoi(s); // get value of n
    for(int i = 0; i &lt; n; i++){
        getline(cin,s);          // read line
        ll open = 0, smiopen = 0, smiclose = 0;
        bool colon = false;      // was the last character a colon?             
        bool balanced = true;
        for(ll j = 0; j &lt; s.size(); j++){
            if(colon){
                if(s[j] == '(') smiopen++;  //you COULD open an expr.
                if(s[j] == ')' &amp;&amp; open &gt; 0) {open--; smiclose++;} // you COULD close an expr.
            }else{
                if(s[j] == '(') open++; // you HAVE TO open an expr.
                if(s[j] == ')') {       // you HAVE TO close an expr.
                    if(open &gt; 0) open--;
                    else if(smiopen &gt; 0) smiopen--;   //open an optional expr. for balance
                    else if(smiclose &gt; 0) smiclose--; //unclose optional close
                    else{ balanced = false; break;}   //not possible to match found ')'
                }
            }
            colon = false; 
            if(s[j] == ':') colon = true;
        }
        if(balanced &amp;&amp; open == 0) cout &lt;&lt; &quot;YES&quot;&lt;&lt;endl;
        else cout &lt;&lt; &quot;NO&quot;&lt;&lt;endl;
    }
}

You might notice smiopen and smiclose could be fused into one variable. But I separated them for clarity.