Member Avatar for 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? :)

Edited by gretty because: n/a
  • 3 Contributors
  • 3 Replies
  • 1K Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by VernonDozier

Dani AI

Generated

was right to think a plain counter is insufficient — matching must respect nesting. 's "pop and check" is the right idea, and 's three rules (ignore non-brackets; push openings; on a closing ensure the stack is non-empty and the popped item matches; final stack must be empty) are exactly what to implement. The stack should only hold opening brackets as you scan left-to-right so order is preserved; pushing the entire string first or using two counters loses nesting and gives false positives for inputs like ([)].

bool balanced(const std::string &s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{' || c == '<') st.push(c);
        else if (c == ')' || c == ']' || c == '}' || c == '>') {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if (!((t=='(' && c==')') || (t=='[' && c==']') ||
                  (t=='{' && c=='}') || (t=='<' && c=='>'))) return false;
        }
    }
    return st.empty();
}

Notes: this runs in O(n) time and O(n) worst-case space. Return false immediately on an unmatched closing bracket. If input may contain quoted text, comments, or language-specific constructs (templates, comparison operators), pre-skip those regions or adapt the scanner so angle brackets are treated appropriately. For brevity you can replace the matching condition with a small map from closing to opening chars.

Recommended Answers

All 3 Replies

Member Avatar for mrnutty

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

Member Avatar for 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;

}
Edited by gretty because: n/a
Member Avatar for 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.
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.