CareerCup

#include <stdio.h>
#include <string.h>
const char* isValidString(char* pStr)
{
	int len=strlen(pStr), index=0, count=0;
	if(pStr[index]==')') return "INVALID STR";
	for(;index<len;index++)
	{
		if(pStr[index]=='(') count ++;
		if(pStr[index]==')') count --;
		if(count < 0) return "INVALID STR";
	}
	return (count == 0)?("VALID STR"):("INVALID STR");
}
int main()
{
	char str[100];
	gets(str);
	printf("%s\n",isValidString(str));
	return 0;
}

a) push when u encouter (
b)pop when u encounter )
c)It means before evry push the stack shud be empty else return false ..

@whataheck - Your would not handle case like '((()))'...it is good for case '()()()' only

Assumption: The string ONLY contains '(' and ')'.

bool check_valid_or_not( string* s)
{
int counter_for_left_paren = 0;
int counter_for_right_paren = 0;
for(int i = 0; i< s.length(); i++)
{
if(s[i] == '(') counter_for_left_paren++;
else counter_for_right_paren++;
if( counter_for_right_paren > counter_for_left_paren)
return false;
}
return (counter_for_left_paren==counter_for_right_paren);
}

Time Complexity:O(n)
Space complexity:O(1)

If anything is wrong, feel free to correct me. Thanks in advance.

I think the stack approach wud work because the question clearly says .. for every ")" should have a preceding "(".
Hence the case '((()))' need not be considered .Wat say ?

store only '(' in stack and for every ')' pop stack and if stack is empty
then it is not welldeformed

also if after traversing the whole string if the stack is not empty
then string is also not welldeformed
u can check for this case '()))(('

public boolean isWellformedString(final String the_string) {
    Deque<Boolean> stack = new ArrayDeque<Boolean>();
    for (int i = 0; i < the_string.length(); i++) {
      switch(the_string.charAt(i)):
        case '(':
          stack.push(true);
          break;
        case ')':
          if (!stack.isEmpty()) {
            stack.pop();
          } else {
            return false;  //if stack is empty, there wasn't a preceding '('
          }
          break;
    }
    return stack.isEmpty();  //you want an empty stack when the loop is done.
  }

boolean WellFormed(String s)
	{
		int len = s.length();
		int cnt =0;
		for(int i=0;i<len;i++)
		{
			if(s.charAt(i) == '(')
			{
				cnt++;
			}
			if(s.charAt(i)== ')')
			{
				cnt--;
				if(cnt<0) return false;
			}
		}
		return((cnt==0)?true:false);		
	}

bool wellformed(char a[]){
int i,count=0;
for (i=0;a[i]!='\0';++i){
if(a[i]=='(') ++count;
else if (a[i]==')') --count;
}
if (count==0) return true;
return false;
}

running time O(n)
space O(1)

#define NULL 0
struct node
{
char s;
struct node *next;
};
struct node *top=NULL;
void push(char c)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->s=c;
if(!top)
{
top=temp;
top->next=NULL;
return;
}
temp->next=top;
top=temp;
}
char pop()
{
struct node *temp;
if(!top)
return('0');
else
temp=top;
top=top->next;
return(temp->s);
}
int isempty()
{
if(!top)
return 1;
else
return 0;

}


int IswellFormed(char str[])
{
int n;
int i;
char c;
n=strlen(str);
for(i=0;i<=n-1;i++)
{
if(str[i]=='(')
push(str[i]);
if(str[i]==')')
c=pop();
if(c=='0')
{
printf("not well formed" );
return 0;
}
}
if(isempty())
{
printf("well formed");
}
else
printf("not well formed");
}
int main(void)
{
char str[100];
gets(str);
IswellFormed(str);
return 0;
}