Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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());
    }
}
share|improve this question

5 Answers 5

up vote 4 down vote accepted

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;
}
share|improve this answer
    
I forgot to mention my method was a question, and it had to be recurssive, but I like your recurrsion much better ;p it does look more recurssive to me... –  user39193 Mar 21 at 22:50

You need to maintain open and closed braces count in your method, to check the validity of the closed braces.

boolean isValid(String s, int i, int open, int closed){
    if(i == s.length()){
        if(open != closed) return false;
        return true;
    }   

    if(s.getChar(i) == '(') open = open+1;

    if(s.getChar(i) == ')'){
        if(open > closed) closed = closed+1;
        else return false;
    } 

    return isValid(s, i+1, open, closed);
}
isValid("a*(b+c)") => true
isValid("((!!(123(x))))") => true
isValid(" (rsd+3)*(-3-a))") => false
isValid("(a((b+c)) ") => false
share|improve this answer
    
can you show me a case where my method doesn't work? –  user39193 Mar 21 at 21:33
    
your program looks good to me and should work with all the test cases as far as I can see. Sorry didn't read your question properly. –  Kevindra Mar 21 at 21:39

Your recursive solution works, as long as the input isn't too long. I don't recommend using recursion for this problem, since a long input could easily cause a crash from stack overflow. An iterative solution would be more appropriate for Java.

The method name isn't descriptive enough. Typically, a function that returns a boolean should be named isSomething() or hasSomething(). The parameter p could also be named better.

The helper function should be made private. It can also be static, since is a pure function that does not rely on any object state.

The code could be written more succinctly.

public boolean hasMatchingParentheses()
{
    return hasMatchingParentheses(head, 0);
}

private static boolean hasMatchingParentheses(CharNode current, int level)
{
    if (current == null)
    {
        return (level == 0);
    }

    switch (current.getData())
    {
      case ')':
        if (level == 0) return false;
        return hasMatchingParentheses(current.getNext(), level - 1);
      case '(':
        return hasMatchingParentheses(current.getNext(), level + 1);
      default:
        return hasMatchingParentheses(current.getNext(), level);
    }
}
share|improve this answer

In a more general case, I would implement a Push Down Automaton using a Stack and pushing open parentheses on the stack and performing a pop for closing ones - Assuring, that the stack isn't empty. So every occuring closing parentheses has to match the last pushed open one.

For simple cases, a counter is sufficient enough.

share|improve this answer

Using stack is optimal solution on this question. I would implement as below-

import java.util.Stack;


public class Parenthesis {

    public static boolean parenthesisCount(String s){
        if (s== null)
            return false;
        int len=s.length();
        int count=0;
        Stack<Character> pStack=new Stack<Character>();
        char ch;
        for (int i=0;i<len;i++){
            ch=s.charAt(i);

            if (ch=='(') {
                pStack.push(ch);
                count=count+1;
            }
            else{
                if ((!pStack.isEmpty()) && ch==')') {
                pStack.pop();
                count=count-1;}


            }
        }
        if (pStack.isEmpty() && count==0)
            return true;
        else
            return false;

    }

    public static void main(String[] args){

        System.out.println(parenthesisCount("(add((sdsds)(sdsds))"));

    }

}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.