Subscribe to andrewsw's Blog        RSS Feed
-----

Matched Brackets (Java/C#)

Icon Leave Comment
Problem: Check a string to see if brackets are correctly matched and don't overlap. Every opening bracket must have a matching closing bracket and these brackets mustn't overlap; so "(hello [there) you]" is wrong, overlapping.

I like the way a stack is used to solve this and decided to revisit it.

Solution:

  • Examine the string from start to end.
  • An opening bracket can be pushed onto the stack.
  • If a closing bracket is encountered then check that the last/top item on the stack is the corresponding opening version of this bracket.
  • If so, then remove (Pop) the matched opening bracket and continue.
  • If not, then this closing bracket is either unmatched or overlaps, so the brackets of the string aren't correct.
  • Or, if the stack is empty, this means that this closing bracket is the first encountered (or doesn't have an opening version) so, again, the brackets aren't correct.
  • Having parsed the whole string, the stack should be empty, because all matched brackets have been removed.
  • That is, if there is anything left on the stack, then the brackets aren't matched.

I was about to write my own version but decided (for some reason) to have a quick look at an existing solution. I found this Java version:
public static boolean isValid(String s) {
    HashMap<Character, Character> map = new HashMap<Character, Character>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
 
    Stack<Character> stack = new Stack<Character>();
 
    for (int i = 0; i < s.length(); i++) {
        char curr = s.charAt(i);
 
        if (map.keySet().contains(curr)) {
            stack.push(curr);
        } else if (map.values().contains(curr)) {
            if (!stack.empty() && map.get(stack.peek()) == curr) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
 
    return stack.empty();
}


It was nice to see that this was very close to what I had intended to write, but it was the use of a HashMap that I want to discuss further. (In C# this would be a Dictionary.)

Even though a hashmap, a dictionary, is a very efficient structure, I think it is unnecessary. A simple string can be used as I will show. In particular, notice that the hashmap is searched first by key (keySet()) then by value (values()).

There is a proposed solution further down on that page that uses strings:
public class Solution {
    public boolean isValid(String s) {
        Stack<character> stack = new Stack<character>();
        String operator = "({[";
        String operator2 = ")}]";
        for (int i = 0; i < s.length(); i++) {
            if (operator.contains(s.substring(i, i + 1))) {
                int index = operator.indexOf(s.substring(i, i + 1));
                stack.push(operator2.charAt(index));


This is also complicated by the use of two strings and using substring() more than once.

Here is the single string that I use "()[]{}". The advantages are:

  • It is a single string. Using two strings it is easy to fail to pair-off the brackets (and less easy to read).
  • We only need to examine, to search, the string once because:
  • 1. if the character we are looking at isn't found, then it isn't a bracket
  • 2. if we find an opening bracket, we can just push it on the stack
  • 3. if we find a closing bracket we don't need to search again for the matching opening version, because it is the character immediately to the left of the closing version we have just found.
  • 4. We can easily add a new pair to the string, "()[]{}<>".

Essentially, we are using a string as a dictionary. The "keys" are the even-indexed items and the "values" are the odd-indexed items.

Point 3 is important. Repeatedly searching a string is not efficient. Of course, this will only ever be a short string, so efficiency here is of no concern. Nevertheless, repeatedly searching or manipulating strings is something that we try to avoid or reduce.

Here is my C# solution using a WinForm with a Button. It shouldn't be too tricky an exercise for you if you wanted the Java version.
    private void button1_Click(object sender, EventArgs e) {
        MessageBox.Show(Matched("(check (this) [and this] ()").ToString());
    }

    public static bool Matched(string search) {
        string brackets = "()[]{}";
        Stack<char> stack = new Stack<char>();

        foreach (char ch in search) {
            int found = brackets.IndexOf(ch);

            if (found == -1) continue;          // ignore, not a bracket
            if (found % 2 == 0) {
                stack.Push(ch);             // opening bracket, push
            } else {
                // it's a closing bracket
                if (stack.Count == 0 || stack.Peek() != brackets[found - 1]) {
                    return false;   // mis-matched
                } else {
                    stack.Pop();    // remove matched opening bracket
                }
            }
        }
        return (stack.Count == 0);
    }


(I used a WinForm as I did consider that I might progress the example to colouring brackets in a RichTextBox, but I decided not to pursue this.)

Notice the use of the code if (found % 2 == 0) { to recognise opening brackets, the even-indexed items. I think it's neat that we are essentially combining the search for keys and values (keySet() and values()) into one operation. If the index isn't even then we must have a closing bracket, and the opening version is to its left.

I doubt that I can claim complete originality for this though. I feel sure that if you/I continued searching we might find that someone has already taken this approach. Still, it's "neat" and a good example of working with a stack.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

December 2019

S M T W T F S
1234567
8 91011121314
15161718192021
22232425262728
293031    

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)

    Categories