Algorithm: Check if string is balanced

[gretty]

Hello

Can you assist me in developing my algorithm?

I have to do this:

Write a C++ function balanced that uses a stack to check that all brackets in a string are balanced.

For eg:

This is a balance string:
This (string) has (balanced {brackets[(now)]} [thanks])

This string is not balanced:
This [[string has (bad} brackets]>)

I am strugling thinking of a way of doing this using stacks.

My idea so far is:

Check each character of a string:
- if the character is any of these "[{(<" then (open.push(1)) - where open is a stack of integers.
- else if the character is any of these "]})>" then (close.push(1)) - where close is a stack of integers.
- else do nothing

If we reach the end of the string & open.size() == close.size() then the string is balanced
, if not then the string is not balanced.

This is the only way I can think of, although it does not really utilise the features of a stack, because I could just use int counters to replace the stacks open & close & it would still work.(i am just counting open & closed brackets).

Any ideas how I could use stacks (LIFO characteristics) to find if a string is balanced? :)

[mrnutty]

Pop each element. Check if there are equal matching braces/brackets...

[gretty]

Pop each element. Check if there are equal matching braces/brackets...

So do you mean:

/* Algorithm
1. store each character of s into stack <char> letters
2. check if letters.top() == "[{(<" (open bracket) - if yes - int open++;
3. check if letters.top() == "]})>" (closed bracket) - if yes int close++;
4. letters.pop();
5. if letters.empty() { if (open == close) { return true; }
    else return false;
*/
bool balanced(string s)
{

     stack <char> letters;
     int open = 0;
     int close = 0;
     
     for (int i=0; i<s.length(); i++) {
          letters.push(s.at(i));
     }
     
     while (!letters.empty()) {
           if (isOpen(letters.top())) {
                open++;
           }
           else if (isClose(letters.top())) {
                close++;
           }
           
           letters.pop();
     }
     
     if (open == close) {
         return true;
     }
     else return false;

}

[VernonDozier]

Well, do you have to do anything with these strings of characters or are you just making sure everything's balanced?

If the latter, there's not a lot to it. First, ignore anything that isn't a bracket of some sort. You push any opening bracket you run into. When you hit a closing bracket, you pop. One, there had better be something to pop. Two, what is popped had better be the corresponding opening bracket to the closing bracket you just encountered. Three, at the end, you'd better have an empty stack.

If any of these three criteria fail at any point, it's unbalanced. If all tests pass, it's balanced.

This [[string has (bad} brackets]>)

Ignore all non-brackets:

[[(}]>)

Go left to right.

1. [ is an opening bracket. Push it.
2. [ is an opening bracket. Push it.
3. ( is an opening bracket. Push it.
4. } is a closing bracket. Pop.
5. Your pop is (, which doesn't match }. Test 2 fails. The string is therefore not balanced.