Check Valid Parentheses

You're given a string consisting solely of (, ), and *. * can represent either a (, ), or an empty string. Determine whether the parentheses are balanced.

For example, (()* and (*) are balanced. )*( is not balanced.

Example:

Input:  s = "(()*"
Output: true

Approach

C++

#include <bits/stdc++.h>
using namespace std;

bool checkValidString(string s)
{
    int n = s.size();
    if (n == 0)
        return true;
    stack<pair<char, int>> st1, st2;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '(')
            st1.push({s[i], i});
        else if (s[i] == '*')
            st2.push({s[i], i});
        else
        {
            if (!st1.empty())
                st1.pop();
            else if (!st2.empty())
                st2.pop();
            else
                return false;
        }
    }
    while (!st1.empty() && !st2.empty())
    {
        if (st1.top().second > st2.top().second)
            return false;
        else
        {
            {
                st1.pop();
                st2.pop();
            }
        }
    }
    if (st1.size())
        return false;
    return true;
}

int main()
{
    string str = "(()*";
    if (checkValidString(str))
        cout << "true";
    else
        cout << "false";
    return 0;
}