"Brackets" Review

Welcome back for another weekly review series!

When you open first "Electronic Station" the first mission that you encounter is the classic "Brackets" mission. This is a simple, but interesting and useful mission. "Brackets" can be solved with a wide variety of methods, and CiO players have certainly come up with some clever and ingenious solutions to it.

Description

You are given an expression with numbers, brackets and operators. For this task only the brackets matter. Brackets come in three flavors: "{}" "()" or "[]". Brackets are used to determine scope or to restrict some expression. If a bracket is open, then it must be closed with a closing bracket of the same type. The scope of a bracket must not intersected by another bracket. In this task you should make a decision, whether to correct an expression or not based on the brackets. Do not worry about operators and operands.

Stack Solution

I've solved this mission myself, using a stack. Iterate a given text symbol by symbol.

• If a character is not a bracket then skip it,
• If a character is an opened bracket then put in the stack,
• If a character is a closed bracket, then try to take the top element of the stack and check whether they form a pair of identical brackets: "()", "[]" or "{}".

If we try to take an element from the stack and it's empty, or after checking all symbols the stack is not an empty, then our expression is wrong.

def checkio(data):
    stack = []  # Yes, we can use deque 
    pairs = {'(': ')', '[': ']', '{': '}'}
    for token in data:
        if token in pairs.keys():
            stack.append(token)
        elif token in pairs.values():
            if stack and token == pairs[stack[-1]]:
                stack.pop()
            else:
                return False
    return not bool(stack)

You can examine this code execution with the Pythontutor service

Stackless Solution

This mission can be solved without using stack and instead with a string method as seen in @blabaster's "Stackless" solution

def checkio(expression):
    s = ''.join(c for c in expression if c in '([{}])')
    while s:
        s0, s = s, s.replace('()', '').replace('[]', '').replace('{}', '')
        if s == s0:
            return False
    return True

As the first solution, we have to "clear" extra text and keep only the brackets. So a string like "{[(3+1)+2]+}+()" become to "{[()]}()". Next we remove all pairs of brackets which are close to each other like "()", "[]" or "{}". If for some step we don't remove anything and the string is not an empty, then the given text is wrong. You can examine this code with Pythontutor - "stackless".

Here's a short, slightly less readable and recursive version of the algorithm in @coells's solution.

import re
EXPR = re.compile('\[\]|\(\)|\{\}|\d|[\+\-\*\/]')
checkio = lambda e, f = '': True if e == '' else False if e == f else checkio(EXPR.sub('', e), e)

"Now They Have Two Problems"

How about regexp -- @LuigiMoro wrote an almost regexp solution. He prepared three regexp expressions and checks if any of it matches, then returns False if they do. But before this we check that the quantity of opened brackets are equal to the closed for each type.

import re
​
pattern_1 = re.compile(".*\{[\w|\+|\-|\*|/|\s]+[\]|\)].*")
pattern_2 = re.compile(".*\[[\w|\+|\-|\*|/|\s]+[\}|\)].*")
pattern_3 = re.compile(".*\([\w|\+|\-|\*|/|\s]+[\}|\]].*")
 
def checkio(expression):​
    if (expression.count("{") != expression.count("}") or
        expression.count("[") != expression.count("]") or
        expression.count("(") != expression.count(")")) :
        return False
 
    return (pattern_1.match(expression) or pattern_2.match(expression) or pattern_3.match(expression)) is None

Fython

I'm not sure why @astynax84 placed "Fython" in technically oneliner solution. Yes, this is a oneliner, but it's been indented for "readability".

checkio = lambda s: reduce(lambda (f, stk), x:
    ((False, None) if not f else (
        (f, ({"[":"]", "{":"}", "(":")"}[x], stk))
        if x in "[({" else (
            (f, stk) if x not in "]})" else (
                (False, None)
                if stk is None or x != stk[0] else
                (True, stk[1])
            )
        )
    )), s, (True, None)) == (True, None)

And with this mind twisted solution I say goodbye for now -- That's all I've got on brackets. If you need any more, go to the hardware store.