Check Balance of Parens, Brackets, and Curly Brackets

  • Thread starter Thread starter fadi_nzr
  • Start date Start date
  • Tags Tags
    Function
AI Thread Summary
The discussion revolves around implementing a function to check if parentheses, brackets, and curly braces in a string are properly matched and nested. The initial code attempts to use a stack but contains several flaws. Key issues include pushing the entire string onto the stack instead of individual characters, leading to incorrect handling of input. The logic for matching closing brackets is also flawed, as it does not correctly check the top of the stack against the expected opening bracket. Participants emphasize the importance of pushing only single characters onto the stack and suggest modifying the push function to accept characters instead of strings. There is a consensus that the current implementation will fail for certain test cases, such as "a(", which should return not balanced but does not due to the lack of proper checks for non-bracket characters. The discussion highlights the need for a clearer approach to handling different characters and ensuring that the stack only contains relevant opening brackets for accurate matching.
fadi_nzr
Messages
14
Reaction score
0
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

Code:
  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
 
Technology news on Phys.org
fadi_nzr said:
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

Code:
  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?
 
ohh, yeah I am not getting what I a, suppose to get. I want to know my mistakes first time dealing with stack
 
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.
 
Did you test it with some test cases? Did it work?

Code:
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?
 
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.
 
mfb said:
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
 
Last edited:
@Fooality: I asked fadi_nzr, not you, sorry for the confusion.

@fadi_nzr: That approach starts to look better now.
fadi_nzr said:
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?).
fadi_nzr said:
if (line == '(') { push(sk, line); }
You are comparing/pushing the whole line here? I would expect the whole logic to use single characters only.
 
mfb said:
@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
 
  • #10
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"?)
 
  • #11
mfb said:
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)
 
Last edited:
  • #12
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.
 
  • #13
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 == ')')
{
cout << top(sk) << endl;
if (top(sk)!="(") return 0;
else { pop(sk); }
}
if (line == '[') { push(sk, line); }
if (line == ']')
{
cout << top(sk) << endl;
if (top(sk) != "[") return 0;
else { pop(sk); }
}
if (line == '{') { push(sk, line); }
if (line == '}')
{
cout << top(sk) << endl;
if (top(sk) != "{") return 0;
else { pop(sk); }
}
}//for
if (elements(sk) == 0) return 1;
else return 0;
}//balanced
 
  • #14
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.
 
  • #15
mfb said:
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 !
 
  • #16
fadi_nzr said:
I tried "a(" and it returned 0 !
That's what mfb is saying.
 
  • #17
mfb said:
@Fooality: I asked fadi_nzr, not you, sorry for the confusion.
.

Oh, sorry I'm new to this forum.
 
  • #18
Mark44 said:
That's what mfb is saying.

how he said the result will be "matching".
 
  • #19
Mark44 said:
That's what mfb is saying.
fadi_nzr said:
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.
 
  • #20
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.
 

Similar threads

Replies
4
Views
2K
Replies
1
Views
3K
Replies
1
Views
3K
Back
Top