Friday, August 06, 2010

bracket matching

Check for brackets matching - curly, square, round, {}[]() - and return boolean.
ex: return true for
{}
{[()]}
{()[]}
return false for
{
}

bool bracketMatching(char[] str):
    bool result = true
    Stack unclosed = new Stack()
    //close-open bracket map, open set, close set
    Hashmap bracketMap = new Hashmap()
    bracketMap.Add('}', '{')
    bracketMap.Add(')', '(')
    bracketMap.Add(']', '[')
    openSet = new Set()
    openSet.Add('{')
    openSet.Add('(')
    openSet.Add('[')
    closeSet = new Set()
    closeSet.Add('}')
    closeSet.Add(')')
    closeSet.Add(']')
    foreach (char c in str):
        if (openSet.has(c)):
            unclosed.Push(c)
        else if (closeSet.has(c)):
            if (unclosed.isEmpty()):
                result = false
                break
            //tos should be open bracket and c close bracket
            char tos = unclosed.Pop()
            if (tos != bracketMap[c]):
                result = false
                break
    if (!unclosed.isEmpty()):
        result = false
    return result


[Hat tip to BR]

No comments:

Post a Comment