CareerCup

Your approach won't work for this case or other similar cases:
)(

The idea should be to use a stack or a count left_count and right_count and at point in time right count should never be greater than left count and in the end both should be zero.

Read my comment carefully( last statement) . If i is negative at any instant then brackets wont match.
)( => i will be -1 for first ')' => brackets wont match.

public static boolean isNested(String AK){
int status=0;
for(int i=0;i!=AK.length();i++){
if(AK.charAt(i)=='('){
status++;
continue;
}
if(AK.charAt(i)==')'){
status--;
if(status<0){
return false;
}
continue;
}
}
return status==0 ? true : false;
}

@ Cerberuz
Sorry i missed that part but still i have one more scenario which i had in mind while posting the stack based approach where in the left and right parenthesis could be from "{, [ , ( , ), ] , }" set.

In that case keeping counters won't help i think. Rather keep pushing the left parenthesis on the stack and when a right parenthesis comes in check the top of the stack for corresponding left parenthesis and pop it till string gets emptied. At that point in time stack should also be empty.



Opinions?

int valid_parenthesis(string str)
{
	 int size_str = str.size();
	 stack<char> stk;
	 for(int i=0; i<size_str; i++)
	 {
		assert(str[i]=='(' || str[i]=='{' || str[i]=='[' || str[i]==')' || str[i]=='}' || str[i]==']');
		
		if(str[i]=='(' || str[i]=='{' || str[i]=='[')	stk.push(str[i]);
		else {
			if(str[i]==')' && stk.top()!='(') ||
				str[i]=='}' && stk.top()!='{') ||
				str[i]==']' && stk.top()!='[') ) {
				return false;
			}
		}
	}
	
return stk.empty() ? true:false;
}

You still don't require stack, use 3 variable i,j,k for each type '(', '{', '['. Moreover with 3 types, this problem is more complex.

You need to take care of invalid cases like :
{ { [ } ] }

And how will you take care of those invalid cases without a stack or something conceptually equivalent?

@Martin I think "SAM((RAT" type of string is not getting Handled, so we can modify your code as..
let me know if wrong...
bool valid_braces(std::string str) {
  int open = 0,close=0;
  for (int i = 0; i < str.length(); i++) {
    if (str[i] == '(') open++;
    else if (str[i] == ')') {
      close++;
    }
  }
if(close==open)
  return true;
else 
 return false;
}

@samrat ur approach ll fail for the cases like tis. "())(". It will return true for tis case whereas it shud return false.

Adding to Cerberuz,Martin,Samrat approach....how abt additional check...checking the last peranthesis character

If its (, even though string has balanced paranthesis..that should be an invalid string

bool valid_braces(std::string str) {
int open = 0,close=0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '(') open++;
else if ((str[i] == ')') {
if(close>open)
return false;
close++;
}
}
if(close==open)
return true;
else
return false;
}