Help

This is a discussion on Help within the C++ Programming forums, part of the General Programming Boards category; You should try to implement the algorithm I've already described: For example: - read one character at a time - ...

  1. #16
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You should try to implement the algorithm I've already described:

    For example:
    - read one character at a time
    - for each opening bracket, push the corresponding closing bracket on the Stack
    - for each closing bracket:
    if the Stack is empty => ERROR
    if the popped value is not the same as current character => ERROR
    - when no more input the Stack should be empty, or there were unmatched opening brackets.
    Counting opening and closing brackets does not help one bit. ([)] has the right number of brackets, but they are not nested properly.

    You need to understand what the stack is for:

    Step 1: Character is "(". Push ")" - the corresponding bracket we'll be expecting. Stack now contains ")".
    Step 2: Character is "[". Push "]". Stack now contains ")]"
    Step 3: Character is ")". Value popped from the stack is "]". There is a mismatch, hence the expression is incorrect. Return false.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  2. #17
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Ohk now this code is working fi9,,, Thanks Anon ,,
    But the assignment say
    The assignment is to write a program that takes a random sized (size max 15) input of brackets from user,AS A STRING, and can validate the sequence.






    Code:
    #include<iostream.h>
    #include<conio.h>
    
    const int MAX=15;
    
    class Stack
       {
       char array[MAX];
       char top;
    
       public:
    
       Stack()
       {
       top=0;
       }
    
       void push(char a)
       {
    	if (top<MAX)
    	{
    	array[top]=a;
    	top++;
    	}
       }
    
     char pop()
     {
     top--;
     return array[top];
     }
    
     int isEmpty()
     {
     return top==0;
     }
    
     };
    
     class BracketChecker
     {
     char name;
     Stack a;
    
     public:
    
     void input()
     {
     cin>>name;
     }
    
     char getinput()
     {
     return name;
     }
    
     int function()
      {
    
    		if (name =='(')
    		{
    		a.push(')');
    		}
    		if (name== '{')
    		{
    		a.push('}');
    		}
    		if (name== '[')
    		{
    		a.push(']');
    		}
    
    		if (name ==')')
    		{
    		a.pop();
    		if (!a.isEmpty())
    		if (name == ')')
    		return 1;
    
    		}
    		if (name=='}')
    		{
    		if (!a.isEmpty())
    		a.pop();
    			if (name== '}')
    			return 1;
    		}
    
    		if (name==']')
    		{
    		if (!a.isEmpty())
    		a.pop();
    			if (name==']')
    			return 1;
    		}
    
    		 if (a.isEmpty()==0)
    			{
    			return 0;
    			}
    	  }
    
    
    };
    
    int main()
    {
    clrscr();
    BracketChecker b;
    for (int i=0;i<12; i++)
    {b.input();
    b.function();}
    if (b.function()==1)
    cout<<"Valid";
    else
    cout<<"Invalid";
    getch();
    return 0;
    }

    Nops its not working fi9 ,,it say the sequence valid ({[}]) although its not =((
    Last edited by Fatima Rizwan; 11-27-2009 at 05:06 AM.

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    So, you need to change it such that you traverse over the characters of the string.

    You seriously need to indent your code properly.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    how to change it??

  5. #20
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    lil bit help =(

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    Let me propose an algorithm for you:
    Code:
    while there are characters in the buffer, obtain the current character
        if the current character is an opening bracket, opening brace, or opening parenthesis
            push the current character's corresponding closing bracket version onto the stack
        else if the current character is a closing bracket, closing brace, or closing parenthesis
            if the stack is empty
                there is a mismatch
            pop from the stack
            if the popped character is not equal to the current character
                there is a mismatch
        else
            ignore the character or otherwise deal with an invalid character
    if the stack is not empty
        there is a mismatch
    else
        everything matches
    Now, use your Stack class, but do not use your BracketChecker class, and implement this algorithm. The buffer here can refer to the input buffer, or it could refer to the string that you read in. Frankly, your BracketChecker class is horrible as-is: it is too tightly coupled to input.
    Last edited by laserlight; 11-27-2009 at 05:35 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    how to know the current character??

  8. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    In the case of a string, you just use a loop index (or a string iterator, if you prefer).

    EDIT:
    Oh yeah, if you are going to implement the algorithm I proposed, look at my update. I realised that I transcribed what anon suggested a little wrongly.
    Last edited by laserlight; 11-27-2009 at 05:36 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Code:
    int function()
      {
       while (name== '\0' )
       {
    
    	for (int j = 0; j <10; j++)
    	{
    		if (name[j] =='(')
    		{
    		 a.push(name[')']);
    		}
    		if (name[j]=='[')
    		{
    		a.push(name[j] == ']');
    		}
    		if (name[j] == '}')
    		{
    		a.push(name['{']);
    		}  }
    
    
    		if (name[j] ==')' || name[j]=='}' || name[j]==']' )
    			{
    			if (a.isEmpty()==0)
    			{
    			return 0;
    			}
    			a.pop();
    			if (a.pop()!= name[j] )
    			return 0;
    
    			else if (a.isEmpty()==0)
    			{
    			return 0;
    			}
    		if (!a.isEmpty())
    		{
    		return 0;
    		}
       }
       else
       return 1;
    
    }
    }


    here is the coding i did following ur algo,, but code is not working

  10. #25
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    Well, a.push(name[')']) is wrong. You had the right method earlier, i.e., a.push(')'). Also, I notice that you are calling pop() twice when you want to call it once. Look carefully at where the final check for whether the stack is empty goes.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #26
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Code:
     int function()
      {
       while (name== '\0' )
       {
    
    	for (int j = 0; j <10; j++)
    	{
    		if (name[j] =='(')
    		{
    		 a.push(')');
    		}
    		if (name[j]=='[')
    		{
    		a.push(']');
    		}
    		if (name[j] == '{')
    		{
    		a.push('}');
    		}
    
    
    		if (name[j] ==')' || name[j]=='}' || name[j]==']' )
    			{
    			if (a.isEmpty()==0)
    			{
    			return 0;
    			}
    			if (a.pop()!= name[j] )
    			return 0;
    			}
    
    
    
    		if (!a.isEmpty())
    		{
    		return 0;
    		}
       		
    		else
       		return 1;
    
    	}
    }
    it says functions containning while are not expanded inline

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    Quote Originally Posted by Fatima Rizwan
    it says functions containning while are not expanded inline
    That should just be a warning that can be ignored.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    whatever i give as input,,, it turns out to be invalid

  14. #29
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,941
    What is your entire current code?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #30
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Code:
    #include<iostream.h>
    #include<conio.h>
    
    const int MAX=15;
    
    class Stack
       {
       char array[MAX];
       int top;
    
       public:
    
       Stack()
       {
       top=0;
       }
    
       void push(char a)
       {
    	if (top<MAX)
    	{
    	array[top]=a;
    	top++;
    	}
       }
    
     char pop()
     {
     top--;
     return array[top];
     }
    
     int isEmpty()
     {
     return top==0;
     }
    
     };
    
     class BracketChecker
     {
     char name[MAX];
     Stack a;
    
     public:
    
     void input()
     {
     cin>>name;
     }
    
     char* getinput()
     {
     return name;
     }
    
      int function()
      {
       while (name== '\0' )
       {
    
    	for (int j = 0; j <10; j++)
    	{
    		if (name[j] =='(')
    		{
    		 a.push(')');
    		}
    		if (name[j]=='[')
    		{
    		a.push(']');
    		}
    		if (name[j] == '{')
    		{
    		a.push('}');
    		}
    
    
    		if (name[j] ==')' || name[j]=='}' || name[j]==']' )
    			{
    			if (a.isEmpty()==0)
    			{return 0;}
    
    			if (a.pop()!= name[j] )
    			return 0;
    			}
    
    
    
    		if (!a.isEmpty())
    		{
    		return 0;
    		}
       		
    		else
       		return 1;
    
    	}
    }
    }
    };
    
    int main()
    {
    clrscr();
    BracketChecker b;
    b.input();
    b.function();
    if (b.function()==1)
    cout<<"VALID";
    else
    cout<<"INVALID";
    getch();
    return 0;
    }

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21