A Dyck word is a sequence of 1s and 1s with the property tha

A Dyck word is 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, +1, -1 +1, -1 is a Dyck word, but +1, -1, -1 +1 is not a Dyck word since the prefix +1 -1 -1

Solution

CheckDyckWord(sequence)

This algorithm works because push is maintaining a postive number and every pop decreases that number by 1. If there are no element on stack means stack is empty and sum of prefix so far is 0. So any further -1 will make prefix sum negative and hence we return that this is not a Dyck word sequence.

If we reach end of sequence then either stack will ahve a +ve sum or 0 sum and hence its a dyck word sequence.