In this problem, you're to write a formula editor. Technically, a formula is an expression, which is a sequence of elements. There are 3 kinds of elements: basic elements (arithmetic operator, parenthesis, digit and letters), matrices and fractions (discussed below).
The editor builds an invisible box for the expression being edited. Since the cells of a matrix are also expressions, each cell has a box enclosing it. Similarly, the denominator and numerator of a fraction are both expressions, so each of them has a box.
In the expression above, there are 5 boxes. F1 is encloses the whole expression, F2 and F3 enclose two matrix cells, F4 encloses the numerator and F5 encloses the denominator.
It's not difficult to see that boxes are nested. If box A directly contain box B, we say box A is the parent box of box B (for example, F1 is the parent of F2 and F3, and F3 is the parent of F4 and F5; If box A and box B have the same parent box, we say they're sibling boxes (for example, F4 and F5 are siblings and F2 and F3 are siblings, too).
At any time, the cursor is always directly contained in a box. It might be to the left of all the elements in the box (i.e. at head position), to the right of all the elements (i.e. at tail position), or between two consecutive elements. If the cursor is between element x and y, and x is to the left (so y is to the right), we say the cursor's immediate left element is x, and immediate right element is y.
The cursor supports six kinds of movements: HOME, END, and four arrow directions. Let A be the inner-most box that contains the cursor, then
Home(End): place the cursor at the head(tail) position of A (it's still directly in A!).
Up(Down): If A has a sibling box to its up(down) direction, place the cursor at the head position of B, otherwise check A's parent box (if A's parent box has a sibling...). If none of A's ancestor boxes have such a sibling box, do nothing for this command.
Left(Right): There are four cases.
The formula is output in ASCII format. Each box is formatted as an ASCII rectangle (though most of them are spaces), which is the horizontal concatenation of the ASCII rectangles of all its elements (inner rectangles). Inner rectangles are aligned with their base lines (will be explained shortly). There are no spaces between consecutive elements, and there are no extra lines or columns between the inner rectangles and the boundary of the outer rectangle.
Each element is also formatted as an ASCII rectangle:
Note that when aligning rectangles horizontally, we fix the position of the widest rectangle, and try to move other rectangles so that their center columns have the same horizontal position of the widest rectangle. When this is not possible (i.e. for rectangles whose width has a different parity from the widest one), we can move these troublesome rectangles 0.5 unit to the left of the ideal position, like this:
There is a special case: if the expression is empty, the formatted ASCII rectangle is an empty line, i.e. its width is zero, but its height is one. Naturally, the empty line is the base line.
The input of the editor is already converted to a sequence of command strings. For each string:
There will be several test cases. Each test case contains a series of command strings, one in each line, ending with command Done followed by an empty line. Note that the resulting formula is not necessarily mathematically correct. There will be at most 1000 commands in each test case, and the whole input size does not exceed 200KB.
For each test case, print the final formula in ASCII form. Print the case number in the first line, then an empty line after the formula. Don't print any trailing spaces, but don't omit empty lines (e.g. there is an empty line at the end of sample output 3).
- 5 Fraction 1 Down 6 Right * Matrix AddCol AddCol 1 Right 2 Right 3 Right * Matrix AddRow AddRow 1 Down 2 Down 3 Done 1 + Fraction 1 Down 1 + Fraction 1 Down 1 + Fraction 1 Down x Up Up Right Right Home Up Done Fraction a Done Matrix Fraction a Down b Matrix Fraction c Down d AddRow e Done
Case 1: [1] 1 - 5---*[1 2 3]*[2] 6 [3] Case 2: 1 1+----------- 1 1+------- 1 1+--- x Case 3: a --- Case 4: a [--------] [ e ] b c [---] d
This problem is tricky. Please make sure your program can pass the test cases in the gift package in the contest website. Don't forget that clarification requests to my email address are always welcome.