Simplifying parenthesis matching algorithm

[siawyoung]

https://github.com/dexterleng/carousell-telebot/blob/master/carousell_query.py#L54

I think you can simplify this to a counter based approach?

OPEN_BRACE = "{"
CLOSE_BRACE = "}"

def find_matching_parenthesis(string, start_index):

    assert(string[start_index] is OPEN_BRACE)

    counter = 1
    for index, char in enumerate(string[start_index+1:]):
        if char is OPEN_BRACE:
            counter += 1
        elif char is CLOSE_BRACE:
            counter -= 1
        if not counter:
            return start_index + index + 1

    raise ValueError("Matching parenthesis not found")

Not sure if I'm missing any edge cases here. Would be good to add some unit tests especially for utility functions like this.

You also probably wrap this around a try/catch to make it a bit more robust:

https://github.com/dexterleng/carousell-telebot/blob/master/carousell_query.py#L51

json.loads will raise an exception (and crash the bot) if the string provided is not valid JSON.

[dexterleng]

@siawyoung looks good to me. I should not have checked if the previous brace is the opposite of the current one since you can just assume it will be valid.

Have to ignore braces inside strings though, so have to flip a is_inside_string boolean. I'll try it out this weekend.

Sick O(1) (if you don't slice the string) space algo.