33. Valid Parentheses

The room was quiet in the way only borrowed spaces ever are. Liina had been given the use of a parish house near the edge of Dorpat, its walls thick, its windows small, as if the building itself preferred containment.

Manuscripts lay everywhere. Old songs, half-remembered legends, careful transcriptions in a neat hand— and between them, marks of hesitation: parentheses, square brackets, braces added later in darker ink.

Liina sat with one page held close to the window.

„I keep opening explanations,“ she said without looking up, „and then forgetting where I began. By the time I close one thought, another has already claimed the space.“

Mihkel took the page from her. A sentence wandered, interrupted by an aside, which itself contained a clarification, which never quite returned to the original voice.

„Nothing here is false,“ Liina continued. „Yet when I read it aloud, the meaning collapses. The listener gets lost.“

Mihkel felt an uncomfortable recognition. Rules within rules. Procedures layered upon procedures. Openings without disciplined return.

„Spoken stories forgive this,“ Liina said softly. „A teller can gesture, pause, recover. But the page remembers everything. It does not forgive imbalance.“

He nodded. Written structure demanded something stricter than inspiration.

Each opening mark was a commitment. Each closing mark a return. To close the wrong one first was not a small error— it was betrayal of structure.

He prepared the tape. Curves. Angles. Braces. Interleaved like thoughts interrupting one another.

The Mill began to move. Not quickly. Not eagerly. It advanced with the caution of something that must remember what cannot yet be resolved.

Mihkel watched in silence. For the first time, he did not wonder whether the machine would finish. He wondered whether it should.

On the input tape you’ll get a non-empty string consisting of different types of parentheses: (), [], {}. Your task is to check if the parentheses are validly nested and closed, and output Y if they are, or N otherwise.

Validity rules:

  • Each opening bracket must be matched with a closing bracket of the same kind.
  • Brackets must close in the reverse order in which they were opened.
  • A closing bracket is valid only if a corresponding opening bracket exists.

For example, if the input tape is () the output tape should be Y.

More valid examples: ()[], {}, ([{}]), ((())), {[()]}
More invalid examples: (, )(, (], ([)], ((()), ())

Sign in to submit your solution.