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). Cursor Movement 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. • If the cursor is at the head(tail) position of A, then place the cursor at the tail(head) position of A’s left(right) sibling B. If there is no such B, place the cursor directly in the A’s parent box C, to the immediate left(right) of A.
2/5 • If the cursor’s immediate left(right) element is a fraction, place the cursor at the tail(head) position of the numerator. • If the cursor’s immediate left(right) element is a matrix with n rows and m rows, then place the cursor to the tail(head) position of the box at row [n/2] and column 1(column m). • If the cursor’s immediate left(right) element is a basic element, then place the cursor to the immediate left(right) of that element. Output Formatting 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: • Basic elements occupy exactly one line, which is also the base line. We use three characters ‘ - ’ (that is, one space at each side) to represent the subtraction operator, and all other elements is formatted as a single character. • A matrix is formatted as follows: first, format all the boxes of the matrix cells, and then arrange them into a matrix. The boxes in the same row are aligned according to the base lines, and the boxes in the same column are aligned horizontally. Consecutive rows are separated by an empty line, and consecutive columns are separated by an empty column. Finally, a pair of square brackets is added to the both sides of base lines for each row. The base line of the whole matrix is the base line of the center row if there are an odd number of rows. Otherwise, the base line of the whole matrix is the center empty line. • A fraction is formatted as follows: first, format the denominator’s box and the numerator’s box, then draw a horizontal line (a sequence of ‘-’ characters) between these two, which is also the base line of the whole fraction. The width of the line is the larger value of two widths, plus 2 (i.e. one more ‘-’ on both sides). The denominator and the numerator are aligned horizontally. 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: XXXX ------ XXX 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. Input Handling The input of the editor is already converted to a sequence of command strings. For each string: • If it contains a single character, it must be a basic element. Insert that element at the cursor, and move the cursor to its immediate right. • If it is ‘Matrix’ or ‘Fraction’, then insert an 1×1 matrix or an empty fraction at the cursor, then move the cursor right once. Note that, before moving the cursor right, the new matrix/fraction is to immediate right of the cursor.
5 Fraction 1 Down 6 Right
Matrix AddCol AddCol 1 Right 2 Right 3 Right
Matrix AddRow AddRow 1 Down 2 Down 3 Done
4/5 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 Sample Output Case 1: [1] 1
Case 4: a [--------] [e] b c [---] d