CareerCup

use a stack and push left brace (3 types ) whenever u encounter on to stack.
for every right braces you encounter check if stack is empty or not matching the top of the stack , if so return false else pop the top.

continue. like this till you traverse the whole string.

Afterwards, just check if stack is empty or not and accordingly return true or false.

Add a 1 for startBracket and -1 for endBracket. As soon as number goes negative, you can declare string as unbalanced. One more condition is that at-last, sum should be 0.

Javascript code:

function isBalanced(str){
  var stack = new Stack();
  for(var c=0;c<str.length;c++){
    var chr = str[c];
    if(isOpenBracket(chr)){
      stack.push(chr);
    }
    else if(isCloseBracket(chr)){
      var openBracket = stack.pop();
      if(!bracketsMatch(openBracket, chr))
        return false;
    }
  }
  return true;
}

int validate(char *str)
{
char stack[100];
int top = 0;
while(*str != '\0')
{
if(*str == '(' || *str == '{' || *str == '[')
{
stack[top++] = *str++; //pushing the opening braces into the stack
}
else if(*str == ')' || *str == '}' || *str == ']')
{
if(top > 0)
{
if(match(stack[--top],*str) == 1)
{
str++;
}
else
{
printf("Braces mismatch $ %c %c $ top %d\n",*str,stack[++top],top);
return 0;
}
}
else
{
printf("Lesser closing braces: %c top %d\n",*str,top);
return 0;
}
}
else
{
printf("Invalid braces\n");
return 0;
}
}
if(top == 0)
return 1;
else
{
printf("Openings braces extra (top %d)\n",top);
return 0;
}
}

Use 3 counter variables, sb, rb and cd for square braces, round braces and curly braces respectively; increment each when its an open brace and decrement when a close brace is encountered. At the end of string all counters have to be zero and reject a string if one of the counters becomes negative!

The thought here is to push the left bracket into stack and whenever we encounter a right bracket, pop the entry from stack and compare against the current one.

Time Complexity: O(n)
Auxiliary Space: O(n) for stack

private static int myFlag = 0;
	private static boolean checkB(String str){
		
		Stack myStack = new Stack();
		
		for (int i = 0; i < str.length(); i++) {
			
			
			if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{')
				myStack.push(str.charAt(i));
			
			if(str.charAt(i) == ')'){
				if('(' != myStack.pop().toString().charAt(0)){
					myFlag = -1;
					break;
				}
			}
			
			if(str.charAt(i) == ']'){
				if('[' != myStack.pop().toString().charAt(0)){
					myFlag = -1;
					break;
				}
			}
				
			if(str.charAt(i) == '}'){
				if('{' != myStack.pop().toString().charAt(0)){
					myFlag = -1;
					break;
				}
			}
		}
		
		if(myFlag == -1)
			return false;
		else return true;
		
	}

If there are more than 1 type of braces:
Keep putting them like numbers as
1 => (
2=> {
3=> [
and -1,-2,-3 as their respective closing braces.

Keep summing up the stack while inserting an element. Keep checking that sum does not turn negative. -ve number means that its mismatch. Also, when you receive a closeBrace, pop one element from stack and sum that with new closeBrace, sum should be 0.

0) Assume: we have const brace variables such as SQURE_BRACE, ROUND_BRACE, CURLY_BRACE
1) For every type of brace, have separate weightCounter
1.1) For curly braces "{}", curlyBraceWeight
1.2) For square braces "[]", squareBraceWeight
1.3) For round braces "()" - roundBracesWeight
2) Initialize all brace weights to zero
3) For every brace in the string
3.1) If it is left brace, set modVal to '+1"; if it is right, set modVal to '-1'
3.2) Check the brace type (using the const brace vars), and add modVal to that brace type's weight
3.3) If this brace type's weight hits negative value - quit the loop and report 'unbalanced'
4) After finishing the string, if any weight is not zero - report 'unbalanced'
5) Otherwise, report 'balanced'.

Assume the following Extra Library API:
- MaxBraceTypes - Returns the max no. of brace types
- GetBraceType() - Returns an integer less than MaxBraceTypes (i.e. type ids are continuous)

We could:
- Have an array of MaxBraceTypes size (inited to zero)
- Step (3.2) would be modifying the weight at that index in array of weights

Thanks,
Laxmi