A Balanced World

Interview

Time limit1sMemory limit128 MB

Summary

For each line ending in a period, decide whether its round and square brackets are properly matched and nested, printing yes or no.

Level: Easy3 of 10
Topics: Stack, String, Implementation
Solved: No attempts yet

Problem

The world must be well balanced — like positive and negative, light and dark, and left and right brackets.

Jeongmin's task is to write a program that, given a string, decides whether the brackets inside it are balanced.

A string may contain two kinds of brackets: round brackets ( ) and square brackets [ ]. A string is balanced when all of the following hold:

Every left round bracket ( pairs only with a right round bracket ).
Every left square bracket [ pairs only with a right square bracket ].
Every right bracket has a matching left bracket somewhere before it.
Every pairing is one-to-one; a single bracket cannot pair with more than one other bracket.
For any two matched brackets, the substring between them must also be balanced.

Help Jeongmin decide whether each given string is balanced.

Input

The input consists of several lines. Except for its last character, each line (string) consists of English letters, spaces, round brackets ( ), and square brackets [ ], always ends with a period ., and is at most 100 characters long.

The input ends with a line containing a single period .; this terminating line is not processed.

Output

For each string, print yes on its own line if it is balanced, or no otherwise.

Hint

A string that contains no brackets at all (for example, a string of only spaces) is also considered balanced.

Examples1

Example 1

Input

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

Expected output

yes
yes
no
no
no
yes
yes