Bracket Checker

i dont want anybody to solve this problem for me ,, i jus want you guys to help me understanding the problem,, i didnt really get which sequence is valid or not,,How should i start solving the problem etc,,any hints regarding member functions n data members!!



Correct Sequence of brackets is always of primary importance both for written programs and mathematical expressions. By correct sequence we mean that for every opening bracket there is a closing bracket. The problem 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 for e.g.
{([]{()})} valid
{[]}(} invalid
[]{{{} invalid
(((}))) invalid
{{{}}}} invalid
Reminder:
• Use stack to solve the problem.
• Use Stack class in some other class that uses stack to validate the sequence.

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 or the top of the Stack is not the same symbol then error, else pop the Stack
- when no more input the Stack should be empty, or there were unmatched opening brackets.

- for each opening bracket, push the corresponding closing bracket on the Stack??
Dint really get it,,


plus here is the code for the stack class the compiler shows no error but output is not right

Code:

---

#include<iostream.h>
#include<conio.h>

class Stack
{
int array[5];
int top;

public:

 Stack():top(0)
 {}

 void push(int a)
 {
 if (0<=top<=6)
 array[top]=a;
 top++;
 }

 int pop()
 {
 if (top>=0)
 top--;
 return array[top];
 }
 };
 int main()
 {
 clrscr();
 Stack b;
 int c;

 for (int i=0; i<=6;i++)
 {
 cin>>c;
 b.push(c);
 }
 for (int j=0; j<=6;j++)
 {
 cout<<b.pop();
 }
 getch();
 return 0;
 }

---

First of all, 'top' should be less than or equal to 4, not 6 (remember: array indexes start at 0). Or even more simply, less than 5. The second problem is that you are reading an int instead of a char.

EDIT: Also, you should check that 'top' is greater than (not greater than or equal to) 0 before decrementing.

The second problem is that you are reading an int, not a char.

dint get you??

And you said that you need to compare the braces and a string why your stack is having int's i think you should have string instead of int in array of stack class as the data member.

Quote:

---

Originally Posted by Fatima Rizwan

The second problem is that you are reading an int, not a char.

dint get you??

---

The user input - it's declared as an integer. When you pass an integer to the 'cin' object, it expects an integral number, eg: 2012, -3114, etc. To get it to read a literal character, eg: '{', '(', etc, you need to declare the variable as a char.

i have created a class of stack which pushes the integers in and when the stack is loaded pops them out..
The compiler shows no errors but there is some logical errori guess,,!!

Code:

---


#include<iostream.h>
#include<conio.h>

const int MAX=6;

class Stack
{
int array[5];
int top;

public:

 Stack()
 {
 top=0;
 }

 void push(int a)
 {
 if (top<MAX)
 array[top]=a;
 top++;
 }

 int pop()
 {
 if (top>0)
 top--;
 return array[top];
 }
 };
 int main()
 {
 clrscr();
 Stack b;
 int c;

 for (int i=0; i<=5;i++)
 {
 cin>>c;
 b.push(c);
 }
 for (int j=0; j<=6;j++)
 {
 cout<<b.pop();
 }
 getch();
 return 0;
 }

---

Quote:

---

i have created a class of stack which pushes the integers in and when the stack is loaded pops them out..
The compiler shows no errors but there is some logical errori guess,,!!

---

You still haven't changed the declaration to the 'char' type, as suggested.

first i want to learn how to make int stack class ,, then i will move to the real problem,, thats why i dint changed the type to char,,,

I see. Well, one thing I just noticed is that the 'push' function still increments 'top' if the maximum is exceeded, since the increment is not on the same line as the assignment before it. If you want to associate multiple statements with an 'if' condition, you have to put brackets around it. Anyway, saying simply that "it doesn't work" is really not sufficent. You need to state what you expect the program to do and why, versus what it actually does when you run it.

EDIT: Ah, you are also comparing 'top' with 'MAX', which is not the actual arrays size. Also, in the part of the code where you are printing the stack contents, you are comparing less than or equal to 6, when it should be less than the array length (which should be 'MAX', but don't forget to change that in the array declaration, as well).

ohk i have amended my program and now its working fine!!

Code:

---

#include<iostream.h>
#include<conio.h>

const int MAX=7;

class Stack
{
int array[MAX];
int top;

public:

 Stack()
 {
 top=0;
 }

 void push(int a)
 {
 if (top<MAX)
 { array[top]=a;
 top++;}
 }

 int pop()
 { if (top==0)
 { cout<<"Stack is Empty";
 return 0;}
 top--;
 return array[top];
 }
 };
 int main()
 {
 clrscr();
 Stack b;
 int c;
 for (int i=0; i<7;i++)
 {
 cin>>c;
 b.push(c);
 }
 for (int j=0; j<2;j++)
 {
 cout<<b.pop()<<endl;
 }
 getch();
 return 0;
 }

---

Coming back to the real problem ,,

Use Stack class in some other class that uses stack to validate the sequence."

what does this mean??

Quote:

---

Originally Posted by Fatima Rizwan

ohk i have amended my program and now its working fine!!

---

Good. But you do need to indent your code properly. Otherwise, it's very difficult to follow.

Code:

---

#include<iostream.h>
#include<conio.h>

const int MAX=7;

class Stack
{
    int array[MAX];
    int top;

    public:

    Stack()
    {
        top=0;
    }

    void push(int a)
    {
        if (top<MAX)
        {
            array[top]=a;
            top++;
        }
    }

    int pop()
    {
        if (top==0)
        {
            cout<<"Stack is Empty";
            return 0;
        }
        top--;
        return array[top];
    }
 };
 
int main()
{
    clrscr();
    Stack b;
    int c;
    for (int i=0; i<7;i++)
    {
        cin>>c;
        b.push(c);
    }
    for (int j=0; j<2;j++)
    {
        cout<<b.pop()<<endl;
    }
    getch();
    return 0;
}

---

Quote:

---

Coming back to the real problem ,,

Use Stack class in some other class that uses stack to validate the sequence."

what does this mean??

---

Go back and read Anon's reply (post #2) to get a good idea of how to do it. Let's say you have the following input:

Code:

---

class A
{
    class B
    {
        void foo( )
        {
       
        }
               
        class C
        {
            void bar( )
            {
           
            }
        }
    }
}

---

So basically, when you encounter an 'opening' symbol, simply push the corresponding 'closing' symbol onto the stack. If you come across a 'closing' symbol, just check the stack. If it isn't what you expected, then there is an error, otherwise, discard the current symbol (pop the stack) and proceed. If there is an attempt to pop an empty stack, or the stack is not empty when you are done, then it is ill-formed.

Code:

---

Coming back to the real problem ,,

Use Stack class in some other class that uses stack to validate the sequence."

what does this mean??

---

It most probably means that you have a stack class (with push, pop, and perhaps top and empty methods) and then you have a class called BracketChecker, perhaps with a method:

Code:

---

bool validate(const std::string& expression);

---

that uses the Stack to get the job done (why it has to be a class is somewhat unclear).

Quote:

---

Originally Posted by Sebastiani

So basically, when you encounter an 'opening' symbol, simply push the corresponding 'closing' symbol onto the stack. If you come across a 'closing' symbol, just check the stack. If it isn't what you expected, then there is an error, otherwise, discard the current symbol (pop the stack) and proceed. If there is an attempt to pop an empty stack, or the stack is not empty when you are done, then it is ill-formed.

---

I am really very sorry. I dint get what you are trying to say =((!!
When we encounter an opening symbol why we push the corresponding closing symbol??

Quote:

---

Originally Posted by Fatima Rizwan

I am really very sorry. I dint get what you are trying to say =((!!
When we encounter an opening symbol why we push the corresponding closing symbol??

---

It's just a convention - you can do it either way, really. Whatever seems most logical to you.

Code:

---

while ( input != 13 )
      {
      if input is '(' or '{' or '[' or ')' or '}' or ']'
          {
          if input is '(' or '{' or '['
              push it into the stack.
          else if input is  ')' or '}' or ']'
              {
              if stack is empty
                      report error.
              pop cell from stack
              if cell "matches input"
                      we are ok.
              else if cell dont "matches input" or stack is empty
                      report error.
              }
          }
      }
  if  the stack is not empty
        report error.

---

How about this??

Very good.

A couple of possible issues to be aware of, though:
1) The stopping condition should be on the null-terminator (0, the end of the string), not a newline (13).
2) The condition 'if cell "matches input"' would be incorrect, considering that if the input, for instance, is a closing bracket, then the cell should be an opening bracket. This is actually why it was suggested to push the 'closing' symbol, as it would make the checking logic a little simpler.
3) It's probably necessary to implement an 'is_empty' member function, or similar.

Everything else looks pretty close to being correct. Try to implement it in code now, and see what you come up with.