Brackets
Input: An expression with different of types brackets as a string (unicode).
Output: A verdict on the correctness of the expression in boolean (True or False).
Example:
checkio("((5+3)*2+1)") == True
checkio("{[(3+1)+2]+}") == True
checkio("(3+{1-1)}") == False
checkio("[1+1]+(2*2)-{3/3}") == True
checkio("(({[(((1)-2)+3)-3]/3}-3)") == False
checkio("2+3") == True
How it is used: When you write code or complex expressions in a mathematical package, you can get a huge headache when it comes to excess or missing brackets. This concept can be useful for your own IDE.
Precondition:
There are only brackets ("{}" "()" or "[]"), digits or operators ("+" "-" "*" "/").
0 < len(expression) < 103
def checkio(expression): OPEN = ('(', '{', '[') CLOSE = (')', '}', ']') stack = [] for alpha in expression: if alpha in OPEN: stack.append(alpha) elif alpha in CLOSE: if len(stack) == 0: return False else: last = stack.pop() if OPEN.index(last) != CLOSE.index(alpha): return False if len(stack) != 0: return False return True #These "asserts" using only for self-checking and not necessary for auto-testing if __name__ == '__main__': assert checkio("((5+3)*2+1)") == True, "Simple" assert checkio("{[(3+1)+2]+}") == True, "Different types" assert checkio("(3+{1-1)}") == False, ") is alone inside {}" assert checkio("[1+1]+(2*2)-{3/3}") == True, "Different operators" assert checkio("(({[(((1)-2)+3)-3]/3}-3)") == False, "One is redundant" assert checkio("2+3") == True, "No brackets, no problem"
これは前にRubyで似たようなのを解いた記憶がある。スタックにどんどん入れていって、調べれば良い。
pythonで定数を扱うなら、リストよりもタプルのほうが高速。
また、指定の値を持つかどうかを調べるときはindex関数を使えばOK.