Consider a sequence of +1's and -1's with the property that the sum of any prefix of the sequence is never negative. For example, the sequence +1, -1, +1, -1 satisfies this property, bu +1, -1, -1, +1 does not, since the prefix +1 -1-1 a sequence and a Stack push(x) and pop() operations.

A matched string is a sequence of {, }, (, ), [, and ] characters that are properly matched. For example, "{{()[]}}" is a matched string, but this "{{()]}" is not, since the second { is matched with a ]. Show how to use a stack so that, given a string of length n, you can determine if it is a matched string in O(n) time