Verifying if an expression conforms to restrictive context-free grammar

Question

I'm trying to write a parser that accepts a toy language for a software project class. Part of the production rules relevant to the question in EBNF-like syntax is given here (there's way more relational operators, but I've removed some of them to keep it simple):

cond_expr   = rel_expr
            | '!' '(' cond_expr ')'
            | '(' cond_expr ')' '&&' '(' cond_expr ')' ;

rel_expr    = rel_factor '==' rel_factor
            | rel_factor '!=' rel_factor ;

rel_factor  = VAR | INTEGER | expr ;

expr        = expr '+' term
            | expr '-' term
            | expr ;

term        = term '*' factor
            | term '/' factor
            | factor ;

factor      = VAR | INTEGER | '(' expr ')' ;

VAR         = [a-zA-Z][a-zA-Z0-9]* ;
INTEGER     = '0' | [1-9][0-9]* ;

I've written more or less the entire parser already. I used recursive descent for majority of the language except for expressions, which I decided to use the shunting yard algorithm to parse (because I couldn't get recursive descent to work even after left recursion elimination/left factoring).

The real problem I have is in the cond_expr rule; shunting yard is too powerful for this grammar i.e the grammar can't accept certain conditional expressions. For example, the expression (x == 1) is not accepted, neither is !(x == 1) || (y == 1). I would use the recursive descent method to check if the expression can be accepted, but the issue is with the rel_expr in cond_expr, rel_expr can be substituted with rel_factor '==' rel_factor or rel_factor '!=' rel_factor, and each rel_factor can be substituted with '(' expr ')'. This leads to ambiguity (idk if that's the correct term) when deciding what branch to take in the cond_expr method upon seeing a '(' token. Something like the below:

Expression cond_expr() {
    if (next() == "!") {
        expect("!");
        expect("(");
        auto cond = cond_expr();
        expect(")");
        return cond;
    } else if (next() == "(") {
        // this will fail for e.g (x + 1) == 2
        expect("(");
        auto cond1 = cond_expr();
        expect(")");
        expect("&&");
        expect("(");
        auto cond2 = cond_expr();
        expect(")");
        return Node("&&", cond1, cond2);
    } else {
        return rel_expr();
    }
}

My current strategy I'm attempting is to first validate that the expression can be accepted by the grammar using some subroutine, then calling the shunting yard algorithm to parse it into the required AST. However, I'm having a lot of trouble writing this validation subroutine. Anyone have any suggestions on any methods to solve this?