Checking string has balanced parentheses

user_50419 0
Viewed 38243

I am reading the Algorithm Design Manual Second Edition and this is from an exercise question. Quoting the question

A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

Question is under stacks,queues and lists category. Here is what I wrote in C#.

const char LeftParenthesis = '(';
const char RightParenthesis = ')';
bool AreParenthesesBalanced(string str, out int errorAt)
{
    var items = new Stack<int>(str.Length);
    errorAt = -1;
    for (int i = 0; i < str.Length; i++)
    {
        char c = str[i];
        if (c == LeftParenthesis)
            items.Push(i);
        else if (c == RightParenthesis)
        {
            if (items.Count == 0)
            {
                errorAt = i + 1;
                return false;
            }
            items.Pop();
        }
    }
    if (items.Count > 0)
    {
        errorAt = items.Peek() + 1;
        return false;
    }
    return true;
}

This works well. But I am not sure that this is the right method to approach this problem. Any better ideas are welcome.

algorithm c#
18 Answers

This will work for combination of (), {} and [].

Also detects errors like: ([)], )[]() and ()(, ...

bool isWellFormatted(string line)
{           
        Stack<char> lastOpen = new Stack<char>();
        foreach (var c in line)
        {               
            switch (c)
            {
                case ')':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '(') return false;
                    break;
                case ']':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '[' ) return false;
                    break;
                case '}':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '{') return false;
                    break;
                case '(': lastOpen.Push(c); break;
                case '[': lastOpen.Push(c); break;
                case '{': lastOpen.Push(c); break;
            }                                                                       
        }
        if (lastOpen.Count == 0) return true;
        else return false;
    }
user_45054460

I would use a queue and a stack, to check for opening and closing match

        var dictionary = new Dictionary<string, string>() {
            { "{", "}" },
            {"[", "]" },
            {"(",")" }
        };


        var par = "{()}";
        var queue = new Queue();
        var stack = new Stack();

        bool isBalanced = true;

        var size = par.ToCharArray().Length;

        if(size % 2 != 0)
        {
            isBalanced = false;
        }
        else
        {
            foreach (var c in par.ToCharArray())
            {
                stack.Push(c.ToString());
                queue.Enqueue(c.ToString());
            }

            while (stack.Count > size/2 && queue.Count > size/2)
            {
                var a = (string)queue.Dequeue();
                var b = (string)stack.Pop();

                if (dictionary.ContainsKey(a) && b != dictionary[a])
                {
                    isBalanced = false;

                }


            }


        }

        Console.WriteLine(isBalanced?"balanced!":"Not Balanced");

        Console.ReadLine();

in the first iteration for example, a ='{' and b ='}' so you do your check whether it is balanced or not

user_15133460

I made it a bit more generic Java

public static boolean isBalanced(String expression)
{
    // pairs at the same index
    List<Character> openers = Arrays.asList('{', '(', '[');
    List<Character> closers = Arrays.asList('}', ')', ']');
    char[] exp = expression.toCharArray();
    Stack<Character> stack = new Stack<>();
    for(Character character: exp){
        if (openers.contains(character))
            stack.push(character);
        if(closers.contains(character)){
            if (stack.empty())
                return false;
            //matching pair should be at the same index
            Character opener = stack.pop();
            int openerIndex = openers.indexOf(opener);
            int closerIndex = closers.indexOf(character);
            if (openerIndex != closerIndex)
                return false;
        }
    }
    return stack.empty();
}
user_5464310

This should work:

public class Balanced {
    public static boolean isbalanced(String input) {
        int open = 0;
        int close = 0;
        for (int i=0; i< input.length();i++) {
            switch (input.charAt(i)) {
                case '{':
                case '(':
                case '[':
                    open++;
                    break;
                case '}':
                case ')':
                case ']':
                    close++;
            default:
                break;
            }
        }
        if (open == close){
            return true;
        }
        else {
            return false;
        }
    }

public static void main(String args[]) {
    System.out.println(Balanced.isbalanced("()"));
}
}
user_61711070

C# 7 or so now also has tuples. You don't need the out argument anymore. As many others pointed out, there is no need for a stack or a queue or alike.
Just a balance counter suffices.

    -- Checks the balance of braces in a string.
    -- Error case 1: More closes than open. We can identify the first culprit by index.
    -- Error case 2: More opens than closes. We return the length of the String, 
    --               indicating that there are closed braces missing.
    -- Good case: As many opens as closes. We return (True,Nothing)
    checkBraces :: String -> (Bool,Maybe Int)
    checkBraces [] = (True,Nothing)
    checkBraces s =
        let (balance,offender) = foldl account (0,-1) $ zip [0..] s in
        if balance == 0 
            then (True,Nothing) 
            else (False,Just $ if -1 == offender then length s else offender)
        where
            account :: (Int,Int) -> (Int, Char) -> (Int,Int)
            account acc@(_,off) _ | off /= -1 = acc     -- Once there was an error we stop looking what happens.
            account acc@(b,off) (i,'(') = (b+1,off)     -- One more open brace.
            account (b,off) (i,')')                     -- One more closed brace.
                    | b <= 0 = (b-1,i)                  -- Ouch. We closed more than we opened!
                    | otherwise = (b-1,off)             -- Okay.
            account acc (i,_) = acc                     -- Some other character (Not in ['(',')'])


    testCases =
        [ ("",True)
        , ("(",False)
        , (")",False)
        , ("))((",False)
        , ("()()",True)
        , ("(()))",False)
        ]

    test = 
        all ((==) True) . fmap testOne $ testCases
        where
            testOne (tc,expected) =
                let (actual,_) = checkBraces tc in
                actual == expected

Side note: The syntax highlighting for Haskell here needs some improvement, right? :)

user_22251040
Related