Validating that all open/close parentheses are correctly matched

It returns true for:

a*(b+c)
()()
(())
((!!(123(x))))

and returns false for:

(a((b+c)) 
)()(
))(( 
(rsd+3)*(-3-a))

As you can see, the logic is simple. Can you confirm for me that it works for all-cases? I mean the logic isn't flawed.

It must be efficient and by that I mean not go over the linked list more than once.

public boolean parentheses()
{
    return parentheses(0,_head);
}

public boolean parentheses(int p, CharNode current)
{
    if (current == null)
    {
        if (p == 0)
         return true;
        else 
         return false;
    }
    else
    {
        if(current.getData() == ')' && p == 0)
         return false;
        else if (current.getData() == '(')
         return parentheses(p+1,current.getNext());
        else if (current.getData() == ')')
         return parentheses(p-1,current.getNext());
        else
         return parentheses(p,current.getNext());
    }
}

Short Answer

Yes, I believe it will be functional....
Dubious Recursion

Calling this method recursive is a problem. It is not a recursive method. Just because it is calling itself does not mean it is a recursive function. What you have is a bad loop. From Wikipedia:

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself).

Your code does not have a base case and a recursive case..... unless you consider current==null to be the base case... but that is just the recursion-terminating statement.

What I mean, is that, consider this loop:

boolean checkParenthesis(CharNode current) {
    int p = 0;
    while (current != null) {
        if (current.getData() == '(') {
             p++;
        } else if (current.getData() == ')') {
             p--;
        }
        if (p < 0) {
            return false;
        }
        current = current.getNext();
    }
    return p == 0;
}

That is how you can write the code iteratively.

Now, if I change it just like this:

boolean checkParenthesis(CharNode current, int p) {
    if (current == null) {
        return p == 0;
    } else {
        if (current.getData() == '(') {
             p++;
        } else if (current.getData() == ')') {
             p--;
        }
        if (p < 0) {
            return false;
        }
        return checkParenthesis(current.getNext(), p);
    }
}

What I am trying to show here is that you essentially have a while-loop that uses the stack to check the end condition.

For a long input, your code will fail with a stack-overflow exception.
Iteration

When you have linked data like you do, the natural solution is to use iteration.

The example I have above shows how it can be done.

I am not sure why you are using recursion at all.
Actual Recursion

If you really want to use recursion, the right way to do it would be to recurse down when you encounter a ( value, and recurse up when you encounter a )

Each recursive level will make sure it has a matching parenthesis.... it will look something like:

// used if there is an error.
private static final CharNode ERRORNODE = new CharNode(....);
private static final CharNode ENDOFDATA = new CharNode(....);

boolean checkParenthesis(CharNode current) {
    current = matchParenthesis(current, true);
    if (current == ERRORNODE) {
        return false;
    }
    // current could be null if there was an unexpected ')' as the very last character.
    return current == ENDOFDATA;
}        

CharNode matchParenthesis(CharNode current, boolean toplevel) {
    while (current != null && current != ENDOFDATA && current != ERRORNODE) {
        if (current.getData() == ')') {
            // found our matching brace
            return current.getNext();
        }
        if (current.getData() == '(') {
            // need to start a sub-level check for a matching brace.
            current = matchParenthesis(current.getNext(), false);
        } else {
            current = current.nextData();
        }
    }
    if (current == null) {
        return toplevel ? ENDOFDATA : ERRORNODE;
    }
    return current;
}

StackExchange Code Review Q#45020, answer score: 5