Java if-statement being skipped

Question

The method below takes in a string and a pattern and returns true if they match each other. A '.' matches 1 char and a '*' matches 0 or more (e.g. expMatch("abc", "a.c") should return true). I added a bunch of print statements to see where I went wrong and it seems like the if statement is being skipped even if the str.length() == 1.

I call it with System.out.println(expMatch("abc", "a*c"));

Here is the code:

public static boolean expMatch(String str, String pat)
{   
    if (str.charAt(0) == pat.charAt(0) || pat.charAt(0) == '.')
    {
        System.out.println("in if");
        System.out.println(str.charAt(0));
        System.out.println(pat.charAt(0));
        System.out.println(str.length());
        if (str.length() == 1)
            return true;
        expMatch(str.substring(1), pat.substring(1));
    }

    else if (pat.charAt(0) == '*')
    {   
        System.out.println("in else");
        System.out.println(str.charAt(0));
        System.out.println(pat.charAt(0));
        if (str.length() == 1)
            return true;
        if (str.charAt(0) == pat.charAt(1)) //val of * = 0
            expMatch(str, pat.substring(1));
        else if (str.charAt(1) ==pat.charAt(1))
            expMatch(str.substring(1), pat.substring(1));           
    }

    return false;           
}

and the output is:

in if
a
a
3
in else
b
*
in if
c
c
1
false

Even if the length is 1 it skips the if? Any idea why? P.S. I'm not looking for the solution, just why the if statement is being skipped.

I suggest you add more logging - I'm sure you're just confusing yourself because the output is hard to understand with the recursion involved. — Jon Skeet, Feb 09 '15 at 21:51
You don't return the value of the recursive calls, so those values are just thrown away. Instead, after the recursive call returns, you always return false. — David Conrad, Feb 09 '15 at 21:53
The `if` statement is `skipped` because you have a bug and you don't yet fully understand what you're doing. That's normal for a newbie. Learn how to debug by using your IDE's facilities and using `println` statements. You'll get it if you work at it. — Hot Licks, Feb 09 '15 at 21:54
string length 1 works for me....ahh its a bug, see Toms comment — Leander, Feb 09 '15 at 21:54
You're returning `true` in the innermost recursion call (is that grammatically correct?). The "outer" calls (that are "wrapped" around the inner call) ignore that returned value and perform that next statements of your method. At the end, each one of them reaches this line: `return false;`. — Tom, Feb 09 '15 at 21:55
You have another logical bug (not only the bug others pointed out). Working code provided below. — peter.petrov, Feb 09 '15 at 22:48

score 6 · Answer 1 · answered Feb 09 '15 at 21:57

6

You always return false from the method at the very end. You are calling expmatch recursively but never using the return value. The code comes in to the first if, recurses (because length is not 1) and upon returning will go to the final return statement which returns false.

answered Feb 09 '15 at 21:57

James Watson

464
2
11

thank you. that actually makes sense. I see where I went wrong. – mjr Feb 09 '15 at 22:03

score 4 · Answer 2 · answered Feb 09 '15 at 21:56

You need to add a return before your expMatch() calls - because the false comes from your last line return false;

What happens is this:

you call expMatch() with the two Strings.
you enter the if clause
the if clause enters expMatch() recursively
you enter the else clause
the else clause enters expMatch() recursively
you enter the if clause again
you leave the expMatch() method
you leave the other expMatch method
false is returned

peter.petrov · Accepted Answer · 2015-02-09T22:56:13.103

Your approach is logically incorrect even if you apply the fixes the others suggested. Try this test case:

System.out.println(expMatch("abddddc", "a*c"));

This is because when you encounter a * in the pattern, you have no way to know how many characters "to eat" from the search string.

To say the least, you need a loop somewhere, not just an if. Let me try to fix it for you (not sure if it's possible though, not sure if you always know which path to take, I mean in your recursion). Think some more about it. Here is another unpleasant test case:

System.out.println(expMatch("adddcac", "a*c")); 
// the * needs to eat dddca (despite the c present in dddca),  
// it should not stop recursing there at that c

I think you need some sort of full search here.
Just an if or a while loop is not good enough.

EDIT: Here is a fixed version with a bunch of nasty tests. I think this is called non-linear recursion (as it's not a single path you try). Not 100% sure though about that term.

public class Test055 {

    public static void main(String[] args) {
        // System.out.println(expMatch("abddddc", "a*c"));

        System.out.println(expMatch("adcax", "a*c"));
        System.out.println(expMatch("adcax", "a*c*"));

        System.out.println(expMatch("adcacm", "*"));
        System.out.println(expMatch("adcacmmm", "a*c"));
        System.out.println(expMatch("adcacmmmc", "a*c"));
        System.out.println(expMatch("adcac", "a*c"));

        System.out.println(expMatch("adcacxb", "a*c.b"));
        System.out.println(expMatch("adcacyyb", "a*c.b"));
        System.out.println(expMatch("adcacyyb", "a*c*b"));

    }

    public static boolean expMatch(String str, String pat)
    {
        // System.out.println("=====================");
        // System.out.println("str=" + str);
        // System.out.println("pat=" + pat);

        if (pat.length() == 0 && str.length() > 0) {
            return false;
        } else if (pat.length() == 0 && str.length() == 0) {
            return true;
        } else if (pat.charAt(0) == '.'){
            return str.length() >= 1 && expMatch(str.substring(1), pat.substring(1));
        }else if (pat.charAt(0) != '*'){
            return str.length() >= 1 && pat.charAt(0) == str.charAt(0) && expMatch(str.substring(1), pat.substring(1));
        }else{
            // Now let's handle the tricky part

            // (1) Look for the 1st non-star in pattern
            int k=-1;
            char ch = ' ';
            for (int i=0; i<pat.length(); i++){
                if (pat.charAt(i) != '*'){
                    k = i;
                    ch = pat.charAt(k);
                    break;
                }
            }

            if (k==-1){
                // (2A) only stars found in pattern, OK, any str matches that
                return true;
            }else{
                // (2B) do full search now checking all  
                // possible candidate chars in str that 
                // match the char ch from pattern
                for (int i=0; i<str.length(); i++){
                    if (str.charAt(i)==ch){
                        boolean b = expMatch(str.substring(i+1), pat.substring(k+1));
                        if (b) return true;
                    }
                }
                return false;
            }
        }
    }
}

Java if-statement being skipped

3 Answers3

Linked