Parenthesis, Left, Right and Asterisk

This is a commonly encountered programming puzzle, let’s take a closer look and see why it’s interesting, in Python.

First, a brief description of the problem:

Given a string of 3 characters: ( ) *

such as:

((*)

(()*

(()))

(*)))

determine whether it’s a valid string or not.

Criteria for whether the string is valid are follows:

1. a left or right parenthesis needs to be closed, like this:

( )

!! 😆 obvious, I know.

2. a * can stand for a left parenthesis, right parenthesis, or nothing.

so a * is a valid string all by itself!

Ok, all of that sounded simple enough, but how do you translate it into a program?

Hmm, if there were no asterisk, the problem is quite easy:

• start from left, go through each character in the string.
• keep a count of left parenthesis, subtract 1 left parenthesis for every right parenthesis encountered.
• if left count dips below 0, the string is invalid. After going through the entire string, if the left count is exactly zero, then it’s a valid string.

def check_valid_001(input):
    left = 0

    lp = '('
    rp = ')'

    for c in input:

        if c is lp:
            left = left + 1
        elif c is rp:
            left = left - 1

        if left < 0:
            return False

    if left == 0:
        return True

    return False

Now, if we try to include *, how do we modify this algorithm?

def what_to_do(input):
    left = 0

    lp = '('
    rp = ')'
    asterisk = '*'

    for c in input:

        if c is lp:
            left = left + 1
        elif c is rp:
            left = left - 1
        elif c is asterisk:
            # what to do?

        if left < 0:
            return False

    if left == 0:
        return True

    return False

Um, there is no immediate obvious solution.

Should we pretend * is a left brace?

elif c is asterisk:
    left = left + 1

This won’t work:

(*

this string would be considered invalid.

Should we pretend * is a right brace?

elif c is asterisk:
    left = left - 1

But then this won’t work:

*)

Hmm, I think the trick behind this is what makes this problem interesting, because it forces you to think outside of the box.

In this kind of situation, it usually pays to go back to the basics, in other words, back to the definitions. What is the definition of an * in the context of this problem?

An asterisk can be used as a left parenthesis if needed, as a right parenthesis if needed, or as nothing if not needed.

Um, that’s a lot of “needed”!

This seems to hint at a new state variable: need

What if I keep a variable called “need right parenthesis”? As I iterate through the characters in the string, whenever I encounter a left parenthesis, I know I’ll need one more right parenthesis, and whenever I encounter a right parenthesis, I’ll need one less right parenthesis.

If, however I encounter an asterisk, since it can be used as a right parenthesis, I’ll need one less right parenthesis as well!

After I iterate through the entire string, if I need exactly zero right braces. then the string is valid!

def check_valid_002(input):
    left = 0
    need_right = 0

    lp = '('
    rp = ')'
    asterisk = '*'

    for c in input:

        if c is lp:
            left = left + 1
            need_right = need_right + 1
        elif c is rp:
            left = left - 1
            need_right = need_right - 1
        elif c is asterisk:
            need_right = need_right - 1

        if left < 0:
            return False

    if need_right == 0:
        return True

    return False

With this new version, the follow string works:

(*

but, if we just add one more asterisk, it would stop working:

(**

since now “need_right” would be negative one at the end.

A way to resolve this is to keep need_right at least zero during each iteration:

need_right = max(need_right, 0)

But then this string is still invalid:

*)

since in this case “left” would become negative one, and we have the condition:

if left < 0:
    return False

We can’t remove this condition, because then strings like “())” would become valid…

So we have to go back to “*)”, in this case * clearly stands for a left parenthesis, so it seems like what we are missing is incrementing “left”:

elif c is asterisk:
    left = left + 1
    need_right = need_right - 1

putting all of the above together we have our final solution!

def check_valid_final(input):
    left = 0
    need_right = 0

    lp = '('
    rp = ')'
    asterisk = '*'

    for c in input:

        if c is lp:
            left = left + 1
            need_right = need_right + 1
        elif c is rp:
            left = left - 1
            need_right = need_right - 1
        elif c is asterisk:
            left = left + 1
            need_right = need_right - 1

        need_right = max(need_right, 0)

        if left < 0:
            return False

    if need_right == 0:
        return True

    return False


def test(validator):

    inputs = [
        '())', '(())', '()()', '(()', '(()())',
        '*', '**', '(*', '*)',
        '(**', '**)', '*()', '((*'
    ]

    for input in inputs:
        print(f'test {input} valid: {validator(input)}')

# print('test 001')
# test(check_valid_001)

# print('test 002')
# test(check_valid_002)

print('test final')
test(check_valid_final)

Plus a unit test for bonus points!