Dyck Paths
InterviewTime limit1sMemory limit1024 MB
Given a correct bracket sequence, draw its Dyck path on a grid of unit squares using / and \ with the fewest possible lines.
- Level
Medium4 of 10
- Topics
- Simulation, String
- Solved
- No attempts yet
Problem
A Dyck path is one way to visualize a correct bracket sequence. It is a path on a grid made of diagonal segments, each joining opposite corners of a unit square. The path starts at the origin. An opening bracket is a segment that rises to the right, and a closing bracket is a segment that falls to the right. The picture shows the Dyck path for (())().
Write a program that draws the Dyck path for a given correct bracket sequence. Use . (ASCII 46) for empty unit squares, / (ASCII 47) for unit squares that contain an upward segment, and \ (ASCII 97) for unit squares that contain a downward segment.
A correct bracket sequence is a sequence of opening and closing round brackets with equal counts, where every prefix has at least as many opening brackets as closing brackets.
Input
A correct bracket sequence is given as input. It is not empty, and its length is at most 100 characters.
Output
Print the picture of the Dyck path for the given correct bracket sequence. Print the fewest possible number of lines. All lines must have the same length, and that length must be the smallest possible for the input.