Check Balance of Parens, Brackets, and Curly Brackets

[fadi_nzr]

Hello

I am writing the balance function that should figure out whether the left and right parens ( ) , the left and right brackets [ ] , and the left and right curly brackets { } are properly matched and nested in the string arg. For instance,

examples "(sldkj[slkdfjk{slkdfjsl(sldkjf(lkjsd)slkdfj)sldkfj}slkdjf]sldkfj)": balanced,
"(((( [[[[ ]]]]{{{{ }}}} ))))": balanced
"([)]": not balanced (even though we have left & right paren and a left & right bracket)
"": balanced, no parens means no mismatch

  bool balanced(const string & line)
{
   Stack sk;
   initialize(sk);
   if (line.size() > STACK_SIZE) die("stack overflow");
   for (unsigned i = 0; i < line.size(); i++)
   {
     switch (line[i])
     {
     case '(':
       push(sk, line);
       if (line[i] == ')')
       {
         if (top(sk)== "(") return 0;
         else  pop(sk);
       }
     case '[':
       push(sk, line);
       if (line[i] == ']')
       {
         if (top(sk) == "[") return 0;
         else  pop(sk);
       }     
     case'{':
       push(sk, line);
       if (line[i] == '}')
       {
         if (top(sk) == "{") return 0;
         else  pop(sk);
       }   
     default:
       ;
     }//switch
   }//for
   
   if (elements(sk) == 0) return 1;
   else return 0;
}//balanced

 

[Mark44]

Hello

I am writing the balance function that should figure out whether the left and right parens ( ) , the left and right brackets [ ] , and the left and right curly brackets { } are properly matched and nested in the string arg. For instance,

examples "(sldkj[slkdfjk{slkdfjsl(sldkjf(lkjsd)slkdfj)sldkfj}slkdjf]sldkfj)": balanced,
"(((( [[[[ ]]]]{{{{ }}}} ))))": balanced
"([)]": not balanced (even though we have left & right paren and a left & right bracket)
"": balanced, no parens means no mismatch

  bool balanced(const string & line)
{
   Stack sk;
   initialize(sk);
   if (line.size() > STACK_SIZE) die("stack overflow");
   for (unsigned i = 0; i < line.size(); i++)
   {
     switch (line[i])
     {
     case '(':
       push(sk, line);
       if (line[i] == ')')
       {
         if (top(sk)== "(") return 0;
         else  pop(sk);
       }
     case '[':
       push(sk, line);
       if (line[i] == ']')
       {
         if (top(sk) == "[") return 0;
         else  pop(sk);
       }    
     case'{':
       push(sk, line);
       if (line[i] == '}')
       {
         if (top(sk) == "{") return 0;
         else  pop(sk);
       }  
     default:
       ;
     }//switch
   }//for
  
   if (elements(sk) == 0) return 1;
   else return 0;
}//balanced

Do you have a question?

 

[fadi_nzr]

ohh, yeah I am not getting what I a, suppose to get. I want to know my mistakes first time dealing with stack

 

[Fooality]

Without going into too much detail, you need to think about the stack as a record of what you've read so far. Add (push) opening brackets onto the stack when encountered, remove (pop) MATCHING closing brackets when encountered with no error, return error iff you encounter a closing bracket that does NOT match the opening bracket on top of the stack, and return success iff you get to the end of the string with the stack completely empty. Your code does not do this.

 

[mfb]

Did you test it with some test cases? Did it work?

switch (line[i])
     {
     case '(':
       push(sk, line);
       if (line[i] == ')')
       {
         if (top(sk)== "(") return 0;
         else  pop(sk);
       }

Can you explain what that part is supposed to do?

For a code like "(a)", if you go through your code line by line, what happens and what is supposed to happen?

 

[Fooality]

No I didn't test it. Even if I had the inclination to, this site doesn't allow detailed answers to homework type questions. What this code is about is Push Down Automata. They are pretty simple, you've got a function that takes the current symbol in the line, and the symbol on top of the stack (or empty stack) as an input. In your case you've got 4 open closing brackets and end of line symbol, same for the stack with an empty stack symbol that makes 5*5 =25 possible inputs. All you need to do is draw up a 5*5 table and decide what needs to be done in each case, and put it into code. If you use a switch statement with 25 possibilities based off this table, its ugly code but will work.

 

[fadi_nzr]

Did you test it with some test cases? Did it work?

Can you explain what that part is supposed to do?

For a code like "(a)", if you go through your code line by line, what happens and what is supposed to happen?

well, I believe there's an error in the switch ( ---- )

I am trying to check each single char of the given string and match it with the cases I have
so let's say the first char was '(' it will be pushed to the stack, but having the following if statement seem useless
that's why I posted my question here I want someone to start with me step by step or give me a push with pseudocode

bool balanced(const string & line)
{
Stack sk;
initialize(sk);
if (line.size() > STACK_SIZE) die("stack overflow");
for (unsigned i = 0; i < line.size(); i++)
{
if (line == '(') { push(sk, line); }
if (line == ')')
{
if (top(sk) != "(") return 0;
else { pop(sk); }
}
if (line == '[') { push(sk, line); }
if (line == ']')
{
if (top(sk) != "[") return 0;
else { pop(sk); }
}
if (line == '{') { push(sk, line); }
if (line == '}')
{
if (top(sk) != "{") return 0;
else { pop(sk); }
}
}//for
if (elements(sk) == 0) return 1;
else return 0;
}//balanced

 

[mfb]

@Fooality: I asked fadi_nzr, not you, sorry for the confusion.

@fadi_nzr: That approach starts to look better now.

if (line.size() > STACK_SIZE) die("stack overflow");

You don't have to push every single letter on the stack (who cares about letters, for example?).

if (line == '(') { push(sk, line); }

You are comparing/pushing the whole line here? I would expect the whole logic to use single characters only.

 

[fadi_nzr]

@Fooality: I asked fadi_nzr, not you, sorry for the confusion.

@fadi_nzr: That approach starts to look better now.
You don't have to push every single letter on the stack (who cares about letters, for example?).

You are comparing/pushing the whole line here? I would expect the whole logic to use single characters only.

I know that I don't want to push the whole line, but instead just the char,
take look at my push function it has a string argument not char.

void push(Stack & stack, const string & item)
{
if (stack.elements == STACK_SIZE) die("Stack Underflow");
stack.data[stack.elements++] = item;
}//push

 

[mfb]

Then you'll need a string with a single char to call your function. Or overload it with the ability to push a char.

(Is that supposed to read "underflow"?)

 

[fadi_nzr]

Then you'll need a string with a single char to call your function. Or overload it with the ability to push a char.

(Is that supposed to read "underflow"?)

I should say something like push(sk, line); // what I meant
but since one of the push function argument is string I cannot say that
so you mean I have to change
void push(Stack & stack, const char& item)

 

[mfb]

There are many ways to implement this, but no matter what exactly you do you should only put the single character onto the stack, not the full line. A function void push(Stack & stack, const char& item) looks like the easiest way.

 

[fadi_nzr]

with this implementation worked for me/ what other ways I can do to push a single char instead of changing the string argument to const char

bool balanced(const string & line)
{
Stack sk;
initialize(sk);
if (line.size() > STACK_SIZE) die("stack overflow");
for (unsigned i = 0; i < line.size(); i++)
{
if (line == '(') { push(sk, line); }
if (line == ')')
{
count << top(sk) << endl;
if (top(sk)!="(") return 0;
else { pop(sk); }
}
if (line == '[') { push(sk, line); }
if (line == ']')
{
count << top(sk) << endl;
if (top(sk) != "[") return 0;
else { pop(sk); }
}
if (line == '{') { push(sk, line); }
if (line == '}')
{
count << top(sk) << endl;
if (top(sk) != "{") return 0;
else { pop(sk); }
}
}//for
if (elements(sk) == 0) return 1;
else return 0;
}//balanced

 

[mfb]

That implementation cannot work. Imagine line="a(". It is clearly unbalanced, but none of your if-statements should match so the for loop does nothing, your stack is empty and the result would be "matching".

Depending on the language and the interpreter, line might get accepted as string, otherwise there is some char to string conversion function.

 

[fadi_nzr]

That implementation cannot work. Imagine line="a(". It is clearly unbalanced, but none of your if-statements should match so the for loop does nothing, your stack is empty and the result would be "matching".

Depending on the language and the interpreter, line might get accepted as string, otherwise there is some char to string conversion function.

I tried "a(" and it returned 0 !

 

[Mark44]

I tried "a(" and it returned 0 !

That's what mfb is saying.

 

[Fooality]

@Fooality: I asked fadi_nzr, not you, sorry for the confusion.
.

Oh, sorry I'm new to this forum.

 

[fadi_nzr]

That's what mfb is saying.

how he said the result will be "matching".

 

[Mark44]

That's what mfb is saying.

how he said the result will be "matching".

With an input string of "a(" your code returns an incorrect value of 0. That was mfb's point - that your code doesn't work correctly.

 

[mfb]

I think 0 means "not matching". But then the code has another problem at this line:
if (elements(sk) == 0) return 1;

Which then means this test case should fail: "ab" - I guess it gives 0 as well, but it is matching and should give 1 (but for sure something different from "a(").

Anyway, here are typical test cases:

a(
ab
a)
()
)(
I would expect that they all give the same result with your code, but some of them are matching and some are not.
(
)
Those two could be interesting as well.