Matching parentheses

Question

I have a string that contains a random order of parenthesis {[()]}. I want to check if for any given parenthesis is there a matching closing one.

Example:

 }}}{{{ //true
 {[]    //false
 {[()]} //true

private static bool checkIfWellFormatted(string inputString)
{

    if (string.IsNullOrEmpty(inputString))
        throw new ArgumentException("String is empty");
    if ((inputString.Length % 2) != 0)
        return false;

    Dictionary<char, int> _inputDictionary = new Dictionary<char, int>();

    foreach (Char c in inputString)
    {
        if (!_inputDictionary.ContainsKey(c))
            _inputDictionary.Add(c, 0);
        else
            _inputDictionary[c] += 1;

    }

    foreach (var item in _inputDictionary)
    {
        char oppKey = '\0';
        if (item.Key == '{')
            oppKey = '}';
        if (item.Key == '}')
            oppKey = '{';

        if (item.Key == '(')
            oppKey = ')';
        if (item.Key == ')')
            oppKey = '(';

        if (item.Key == '[')
            oppKey = ']';
        if (item.Key == ']')
            oppKey = '[';

        if (_inputDictionary.ContainsKey(oppKey))
        {
            var value = _inputDictionary[oppKey];
            if (value != item.Value)
                return false;

        }
        else
            return false;


    }

    return true;
}

Here, the second iteration over the dictionary has \$O(n)\$ complexity. Can I improve its time complexity?

A better definition of the problem would help here. If all you need is to count opening and closing marks and make sure the numbers match, that's less involved than caring whether they overlap and suchlike. — cHao
– cHao, Commented Feb 10, 2017 at 17:00
@t3chb0t I'd say yes, as long as all present parentheses have they're opening/closing partner in the string it's fine. — Denis
– Denis, Commented Feb 10, 2017 at 19:01
@Denis mhmm, but the examples show only properly nested ones so this is not so obvious. — t3chb0t
– t3chb0t, Commented Feb 10, 2017 at 19:07

cHao · Accepted Answer · 2017-02-10 19:18:45Z

One thing you can do is insert beforehand the characters you want to track.

    var _inputDictionary = new Dictionary<char, int>();

    foreach (char c in "{}[]()")
    {
        _inputDictionary.Add(c, 0);
    }

At that point, you can avoid counting every char, and just count the ones you care about.

    foreach (char c in inputString)
    {
        if (_inputDictionary.ContainsKey(c)) _inputDictionary[c] += 1;
    }

And when you're done, rather than having potentially thousands of chars (because you don't restrict input), _inputDictionary always only contains exactly the (currently 6) chars you care about.

Now, as for checking those, since you already know what keys you have and don't have to be paranoid about nulls and such, you can simplify it down to something like

    return _inputDictionary['{'] == _inputDictionary['}']
        && _inputDictionary['('] == _inputDictionary[')']
        && _inputDictionary['['] == _inputDictionary[']']
    ;

All together:

private static bool checkIfWellFormatted(string inputString)
{
    // Just so it's said, by the definition you've given in the question,
    // "" is vacuously well-formatted. (There is a matching delimiter for
    // every one of the 0 chars in the string.) I'd suggest only throwing
    // on null and letting "" be checked (or just return true, considering
    // you already know the result).
    if (string.IsNullOrEmpty(inputString))
        throw new ArgumentException("String is empty");

    // This can speed up the comparison, but only if you outlaw any other
    // characters in the string. Since you don't do that in any way, it
    // simply leads to incorrect answers.
    // if ((inputString.Length % 2) != 0)
    //     return false;

    Dictionary<char, int> _inputDictionary = new Dictionary<char, int>();

    foreach (char c in "{}[]()")
    {
        _inputDictionary.Add(c, 0);
    }

    foreach (char c in inputString)
    {
        if (_inputDictionary.ContainsKey(c)) _inputDictionary[c] += 1;
    }

    return _inputDictionary['{'] == _inputDictionary['}']
        && _inputDictionary['('] == _inputDictionary[')']
        && _inputDictionary['['] == _inputDictionary[']']
    ;
}

I was thinkin in second iteration we can use dictionary.ElementAt() method but then since we are iterating over dictionary the complexity will be still O(n).The thing here is I am trying to make a new problem statement by modifying balancing paranthesis algo stackoverflow.com/questions/2711032/… I am just trying to come with something new — Rohit
– Rohit, Commented Feb 10, 2017 at 17:13
Balanced parens is a whole different thing than what you seem to be trying to do. Especially with three different types of delimiters, you'll need a stack in order to do it decently. — cHao
– cHao, Commented Feb 10, 2017 at 17:17
When you're tallying every character, O(n) can matter. But it isn't really an issue here when you know n=6. Once that's defined, it's no longer O(n) -- it's more like O(6). it does the same amount of work no matter how many chars you've tallied. — cHao
– cHao, Commented Feb 10, 2017 at 17:19

coderodde · Accepted Answer · 2017-02-10 17:53:31Z

You could evict the count dictionary altogether and use three counters. Next, you scan each character and increment/decrement the corresponding counter. The answer is true if after scanning all the characters all three counters are zero. For example, if we scan [, we increment the counter for [ and ]; if we scan ], we decrement that very same counter. (Before the scan all counters are set to zero.)

All in all, I had this in mind:

private static bool WellFormatted(string inputString)
{
    int braceCount = 0;         // Counts '{' and '}'.
    int parenthesisCount = 0;   // Counts '(' and ')'.
    int squareBracketCount = 0; // Counts '[' and ']'.

    foreach (char c in inputString)
    {
        switch (c)
        {
            case '{':
                braceCount++;
                break;

            case '}':
                braceCount--;
                break;

            case '(':
                parenthesisCount++;
                break;

            case ')':
                parenthesisCount--;
                break;

            case '[':
                squareBracketCount++;
                break;

            case ']':
                squareBracketCount--;
                break;
        }
    }

    return braceCount == 0
        && parenthesisCount == 0
        && squareBracketCount == 0;
}

Also, from mathematical perspective, I would accept the empty string as a valid "parenthezation."

\$\begingroup\$ This solution is about 6x faster then the accepted one. \$\endgroup\$

t3chb0t
– t3chb0t

2017-02-11 06:16:51 +00:00
Commented Feb 11, 2017 at 6:16 — t3chb0t
– t3chb0t, Commented Feb 11, 2017 at 6:16

Stack Exchange Network

Matching parentheses

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Matching parentheses

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions