# 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()
{
}

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


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

• 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 '14 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

• can you show me a case where my method doesn't work? – user39193 Mar 21 '14 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 '14 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()
{
}

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


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.

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){