Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Approach

Java

import java.util.Stack;

public class ValidParenthesisString {
    public static void main(String[] args) {
        String str = "()";
        System.out.println(checkValidString(str));
    }

    static boolean checkValidString(String s) {
        int n = s.length();
        if (n == 0)
            return true;
        Stack<Pair> st1 = new Stack<Pair>();
        Stack<Pair> st2 = new Stack<Pair>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(')
                st1.add(new Pair(s.charAt(i), i));
            else if (s.charAt(i) == '*')
                st2.add(new Pair(s.charAt(i), i));
            else {
                if (!st1.empty())
                    st1.pop();
                else if (!st2.empty())
                    st2.pop();
                else
                    return false;
            }
        }
        while (!st1.empty() && !st2.empty()) {
            if (st1.peek().getSecond() > st2.peek().getSecond())
                return false;
            else {
                {
                    st1.pop();
                    st2.pop();
                }
            }
        }
        if (st1.size() > 0)
            return false;
        return true;
    }

    static class Pair {
        private char first;
        private int second;

        public char getFirst() {
            return first;
        }

        public void setFirst(char first) {
            this.first = first;
        }

        public int getSecond() {
            return second;
        }

        public void setSecond(int second) {
            this.second = second;
        }

        public Pair(char first, int second) {
            super();
            this.first = first;
            this.second = second;
        }

    }
}

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;
}