Problem 1006: Marquee Magic

(ACM S.E. U.S.A. Regional 2003, problem 6)

Description

We all know how movies tend to follow trends.one year may see lots of asteroid movies while the next will have lots of alien attack movies. There are also trends in movie names. XXX² is scheduled for a 2005 release, so a Hollywood pundit has determined that the next trend in movies will be using equations as their names. But this causes a real problem for those loyal employees who have to create the marquees. You are to write a program to help them.

Programmers are used to seeing a single-line representation of an equation with the caret symbol indicating the elevation of some base to some power (e.g., x^2 for the base x raised to the second power). Marquee managers are not as familiar with this notation. Your program should transform the single-line representation into a two-line form that are more amenable to putting on a movie marquee. So, for example, if the movie title is a line like:
x^2+3y^2+r
It would be displayed on the marquee as the two lines:

That is, the '^' will be removed, and the exponent will be moved to the line above the rest of the equation. All extra space will be removed from the equation, except that the operators will have exactly one blank before and after them. Your program should take a movie title in the single line format and produce the two-line format.

Input Format

The input file contains one or more single-line expressions. Each expression is guaranteed to be between 1 and 80 characters long. An expression is defined by the following BNF:

<expression>	:==	<term> { <operator> <term> }
<operator>	:==	'+' \| '*'
<term>	:==	<base> [ '^' <exponent> ]
<base>	:==	<unsigned integer> \| [ <unsigned integer> ] <character>
<exponent>	:==	[ '-' \| '+' ] <unsigned integer>

In English, an expression is a term, followed by zero or more operator/term pairs. An operator is either '+' or '*'. A term is a base, followed optionally by a caret ('^') and an exponent. An exponent is an unsigned integer with an optional sign. A base is either an unsigned integer or an optional unsigned integer, followed by a single character.

There may be blanks before or after any elements of an expression. A character is a single lower case letter and an integer is any collection of 1 or more digits.

The end of the input data is marked by the end of the file.

Output Format

For each single-line expression in the input, output a two-line representation of the expression. The first line will contain the <exponent> elements, with a leading sign only if the exponent is negative. The first character of the exponent should be aligned immediately to the right of the right-most character of its base. The last character of the exponent should be aligned immediately to the left of the blank in front of a following operator (if there is one). The second line will contain the <operator> and <base> elements. There should be a blank immediately before and after each operator. There should be no blanks at the ends of lines. An empty line should be printed after each two-line representation.

Since blanks cannot be read by the marquee manager, you should print a period ('.') everywhere there should logically be a blank.

Sample Input

x^2+y^2   +r
      x +  2 ^ 2  +0^1*  3^+3
123^2+12b^-12+c^+12

Sample Output

.2....2
x..+.y..+.r

.....2....1....3
x.+.2..+.0..*.3

...2......-12....12
123..+.12b....+.c