Checking string has balanced parentheses

Question

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.

Might check out http://refactormycode.com/, which is more geared toward this sort of thing. — Larsenal, Sep 04 '09 at 17:41
Yes this is quite right way and is also used to parse mathematical expression. — TheVillageIdiot, Sep 04 '09 at 17:42

nlucaroni · Accepted Answer · 2009-09-04T18:08:59.327

12

I think this is the intention, but really you just need to decrement and increment a counter if you are only dealing with parenthesis. If you are dealing with the pairings of square brackets, angle brackets, curly braces or whatever character pairing you'd like to use, you'll need a stack like you have done.

You can also use a list, pulling the head element off and on, but really a stack is probably implemented as a list anyway --at least it is in ocaml.

edited Sep 04 '09 at 18:08

answered Sep 04 '09 at 17:45

nlucaroni

47,556
6
64
86

Yes. In this case, simple implementation would be to increment and decrement a variable. But the requirement is to use any of the data structures. Thanks for the help. – Navaneeth K N Sep 04 '09 at 17:48
3

A naive counter implementation would check only that the value is zero at the end. To answer this question, you would need to immediately fail if it goes negative and also identify the first excess open if it ends up positive. I don't think this will be any easier than the algorithm shown by Appu. As for data structures, it's going to be a stack, whether it's implemented as a linked list or not. In fact, it would work fine implemented over an array that's as large as the string. Or, in the recursive example, we use the real stack. – Steven Sudit Sep 04 '09 at 17:52
@Appu: It fails the second part, of identifying the offending parenthesis. – Steven Sudit Sep 04 '09 at 17:53
1

@Steven: It finds the first offending parenthesis index and assign to errorAt variable. – Navaneeth K N Sep 04 '09 at 17:56
@Steven: The chapter isn't about recursion that's why I didn't bring it up. Also, strings are arrays here, and you get no advantage from recursion since you'd be carrying around a counter to access the string elements. – nlucaroni Sep 04 '09 at 18:10
@Steven: Why wouldn't you find the offending parenthesis by using a counter? As you iterate over the array you +/-1, and if that is ever negative, you've found the offending parenthesis. The point of using a counter over a stack is that you're holding meaningless characters in a stack, in no way does the stack give you anything with it's existence. – nlucaroni Sep 04 '09 at 18:14
@ncluaroni: There are two failure modes. The easiest is when you hit an close parenthesis but there is no unaccounted for open parenthesis before it. You can then return the current index as the failure point. The harder one is when you get to the end of the string and have one or more opens without closes. How, without something like a stack, would you determine which open is superfluous? – Steven Sudit Sep 04 '09 at 18:34
@Appu: Yes, your code does do that. I was saying that the algorithm suggested by nclcaroni, which uses a counter instead of a stack, cannot do so. – Steven Sudit Sep 04 '09 at 18:35
@ncluaroni: Depending on the language and platform, using the native stack may or may not be faster than using a stack class based on an array and index. It would, however, be more elegant. – Steven Sudit Sep 04 '09 at 18:41

Russell Stephan · Answer 2 · 2012-11-09T15:38:46.407

    static public bool CheckForBalancedBracketing(string IncomingString)
    {
    /*******************************************************************
     * The easiest way to check for balanced bracketing is to start    *
     * counting left to right adding one for each opening bracket, '(' *
     * and subtracting 1 for every closing bracket, ')'.  At the end   *
     * the sum total should be zero and at no time should the count    *
     * fall below zero.                                                *
     *                                                                 *
     * Implementation:  The bracket counting variable is an unsigned   *
     * integer and we trap an overflow exception.  This happens if the *
     * unsigned variable ever goes negative.  This allows us to abort  *
     * at the very first imbalance rather than wasting time checking   *
     * the rest of the characters in the string.                       *
     *                                                                 *
     * At the end all we have to do is check to see if the count       *
     * is equal to zero for a "balanced" result.                       *
     *                                                                 *
     *******************************************************************/
        const char LeftParenthesis = '(';
        const char RightParenthesis = ')';
        uint BracketCount = 0;

        try
        {
            checked  // Turns on overflow checking.
            {
                for (int Index = 0; Index < IncomingString.Length; Index++)
                {
                    switch (IncomingString[Index])
                    {
                        case LeftParenthesis:
                            BracketCount++;
                            continue;
                        case RightParenthesis:
                            BracketCount--;
                            continue;
                        default:
                            continue;
                    }  // end of switch()

                }
            }
        }

        catch (OverflowException)
        {
            return false;
        }

        if (BracketCount == 0)
        {
            return true;
        }

        return false;

    }  // end of CheckForBalancedBracketing()

consider the case where the input is: ')))(((' . Wouldn't this return true according to your algorithm but that's not balanced — AlwaysNull, Jan 23 '16 at 18:07
@AlwaysNull - No, that would cause an OverflowException, because when the first RightParenthesis is detected, the BracketCount-- would cause the uint to be set to -1. — stevejoy32, Aug 29 '17 at 18:40

score 7 · Answer 3 · answered Oct 25 '18 at 20:26

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;
    }

score 2 · Answer 4 · answered Feb 13 '12 at 15:03

Remove all non-'(' and -')' characters from an input string. This gives you a string of '(' and ')' only.
If the string has odd length, return false.
Else, start reading along our string, adding +1 to a "signature" for each '(' and -1 for each ')'; if this signature is ever negative, return false.
Return true.

score 1 · Answer 5 · edited Apr 13 '15 at 14:16

using System;
class Solution
{
    public int solution(string S)
    {
        int x1 = 0;
        int x2 = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == ')')
                if (x1 <= 0) return 0;
                else x1--;
            else if (S[i] == '(')
                x1++;
        }
        if (x1 == 0)
            return 1;
        else
            return 0;
    }
}

Yadira Garnica · Answer 6 · 2020-05-14T14:57:36.673

1

Time order O(n) and spatial order O(1)

public static bool IsBalanced(string input)
{
   int count = 0;
   for (int i = 0; i < input.Length; i++)
   {
       if (input[i] == '(') count++;
       if (input[i] == ')') count--;
       if (count < 0) return false;
    }
    if (count == 0) return true;
    return false;
}

edited May 14 '20 at 14:57

answered Oct 30 '15 at 05:47

Yadira Garnica

59
5

carlosJ · Answer 7 · 2019-02-07T09:01:32.467

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

score 1 · Answer 8 · answered May 19 '19 at 23:38

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();
}

score 0 · Answer 9 · answered Aug 30 '12 at 20:12

int i;
int len; 
char popped;
stack<char> st;
string a = "({<<";
len = a.length();

for(i=0;i<len;i++)
{
    if(a[i] == '<' || a[i] == '(' || a[i] == '[' || a[i] == '{')
    {
        st.push(a[i]); 
        continue;
    }
    if(a[i] == '>' || a[i] == ')' || a[i] == ']' || a[i] == '}')
    {
        if(st.empty())
        {
            cout << "stack is empty, when popped , not balanced" << endl;
            return 0;
        }
        else
        {
            popped = st.top(); 
            st.pop();
            if (!((a[i] == '>' && popped == '<') || (a[i] == ')' && popped == '(') || (a[i] == '}' && popped == '{') || (a[i] == '>' && popped == '<'))) //ok
            {
                cout << "not balanced on character" + std::string(1,a[i]) << endl;
                return 0;
            }
        }

    }

}
if(st.empty())
{
    cout << "balanced" << endl;
}
else
{
    cout << "not balanced stack not empty" << endl;
}

score 0 · Answer 10 · answered Sep 04 '09 at 17:48

0

As TheVillageIdiot said, it's fine. You could also implement it recursively, which might be more elegant, or might not. Finally, you might want to require that matching parentheses contain something valid between them, so as to allow "(a)" but not "()".

answered Sep 04 '09 at 17:48

Steven Sudit

19,391
1
51
53

1

This answer has had 2 downvotes with 0 explanations. I sense an imbalance. So if you have a reason for your downvote, I suggest you share it. – Steven Sudit Sep 04 '09 at 18:46

score 0 · Answer 11 · answered Sep 04 '09 at 17:50

0

Why have a return value and an out parameter that give the same information?

You could return an int: -1 = balanced, otherwise the index of the error.

answered Sep 04 '09 at 17:50

Bill

14,257
4
43
55

I thought about it. But some how I felt this pattern is better suited here. Thanks for the help. – Navaneeth K N Sep 04 '09 at 17:53
@Bill: You would want to call the method FindInvalidParenthesis, then. Then it would make sense for it to return -1 on failure, and the index on success. Having said that, this Try* interface, which returns a success flag while passing the actual value as an out parameter is in many ways cleaner. – Steven Sudit Sep 04 '09 at 18:43
That's a good point, a name-change would be in order under this suggestion. But having to set two values and check two values instead of one to determine the result of the function? I'm afraid I don't see how that is cleaner. – Bill Sep 04 '09 at 19:37

score 0 · Answer 12 · edited Apr 26 '13 at 07:53

Checking balanced parentheses
package parancheck;

import java.util.EmptyStackException;
import java.util.Stack;

public class ParnCheck 
{
    public static void main(String args[])
    {
        int pu = 0;
        int po = 0;
        String str = "()())";
        System.out.println(str); 
        Stack st = new Stack();
       for(int i=0; i<str.length();i++)
       {
        if(str.charAt(i)=='(')
        {
           doPush(st, str.charAt(i));
           pu++;
         }
        else 
        {
             try
              {
                doPop(st);
              }
             catch(EmptyStackException e)
              {
                System.out.println("");
              }
              po++;
        }
     }


       if(pu == po)
       {
           System.out.println("Correct");
       }
       else
       {
           System.out.println("Wrong");
       }

    }
    static void doPush(Stack st,char ch)
    {
        st.push(ch);
    }
    static void doPop(Stack st)
    {
        char c = (char)st.pop();
    }
}

score 0 · Answer 13 · answered Sep 17 '13 at 18:44

import java.util.Stack;

public class CheckBalancedParenthesis {

    public static void main (String args[]){
        CheckBalancedParenthesis checker = new CheckBalancedParenthesis();
        System.out.println(checker.checkBalancedParenthesis("{}}{}{}{}{}"));
    }

    public boolean checkBalancedParenthesis(String pattern){
        Stack stack = new Stack();
        for(int i = 0; i < pattern.length();i++){
            char c = pattern.charAt(i);
            if(c == '{'){
                stack.push(c);
            }else if (c == '}'){
                if(!stack.isEmpty()){
                    stack.pop();
                } else{
                    System.out.println("Error at - " + i);
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

score 0 · Answer 14 · answered Feb 29 '16 at 12:06

Here is simple solution to validate the brackets :
1. Keep Starting brackets and Ending brackets in a string.
2. Loop through given to whom we want to validate and check for following logic :

              a) If item is in starting brackets, PUSH IT IN STACK
              b) If item is in ending brackets, Compare its index(in ending bracket) with stack's top item                   index (in starting brackets).
              c) If index are same POP TOP ITEM OF STACK. Else its Invalid string.
              d) Final step, check for stack if it has item/s, it means its invalid string.

    string starters = "({[<";
    string enders = ")}]>";
    Stack stack  = new Stack();
    foreach(char c in txtValue.Text.Trim())
    {
        if(starters.Contains(c))
        {
            stack.Push(c);
        }
        else if (enders.Contains(c))
        {
            if (stack.Count > 0)
            {

                if (enders.IndexOf(c) == starters.IndexOf(Convert.ToChar(stack.Peek())))
                {
                    stack.Pop();
                }
                else
                {
                    lblResult.Text = "Invaluid string";
                }
            }
        }
    }

    if(stack.Count == 0)
    {
        lblResult.Text = "Valid string";
    }
    else
    {
        lblResult.Text = "InValid string";
    }

You can use the result of `String.IndexOf(Char)` as an indication of _contains_. — greybeard, Feb 29 '16 at 12:17

score 0 · Answer 15 · answered Mar 23 '16 at 14:13

0

Piggy back on @Russell's idea:

public class BalancedBrackets
{
    private readonly char[] _leftBrackets = new char[] {'[', '(', '{', '<'};
    private readonly char[] _rightBrackets = new char[] {']', ')', '}', '>'};

    public bool IsBalanced(string input)
    {
        int count = 0;
        foreach (var character in input.ToCharArray())
        {
            if (_leftBrackets.Contains(character)) count++;
            if (_rightBrackets.Contains(character)) count--;
        }
        return count == 0;
    }
}

answered Mar 23 '16 at 14:13

Stan Bashtavenko

1,025
11
16

This doesn't take into consideration the order. For example ([)] is valid with your solution – Hassen Ch. Oct 17 '17 at 19:49
Yes, a better way would be this https://github.com/bashtavenko/BaseDataStructuresAndAlgorithms/blob/a03abdd50fb56c72f480fb6b5aa36898fb4aac71/Code/NumbersEtc/BalancedBrackets.cs – Stan Bashtavenko Oct 21 '17 at 16:07

score 0 · Answer 16 · answered Aug 03 '17 at 13:30

Here's a one liner for C# using System.Linq:

expression.Aggregate(0, (state, ch) => state == -1 ? -1 : state + (ch == '(' ? 1 : ch == ')' ? -1 : 0)) == 0

it utilizes the fact that string is in fact IEnumerable of chars so we can run Aggregate function on it. We increase the counter by 1 when we encounter the '(' char and decrease it by 1 on ')' char. Once we reach the negative value of -1 we stay there to indicate the invalid state.

It doesn't have any early exit implemented so it will be slower than most implementations presented here but maybe someone will find it useful :)

score 0 · Answer 17 · answered Aug 18 '18 at 21:19

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("()"));
}
}

score 0 · Answer 18 · answered May 20 '19 at 01:46

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? :)

Checking string has balanced parentheses

18 Answers18

Linked

Related