Equation Elation

The author of an elementary school algebra text book has approached you to write a program to solve simple algebra equations. The author wants to use a program to avoid human errors in preparing the solutions manual. The text book author will provide a text file of the simple problems for your problem to solve. All of the problems will be in the form of an algebraic equality. The specific syntax of the problems will be an algebraic statement consisting of integer constants and the four basic arithmetic operators, an equal sign, and a variable. For example:

12 - 4 * 3 = x

For the solutions manual the problem is not just to be solved, but solved one step at a time. For the above input line, the corresponding output would be:

12 - 4 * 3 = x
12 - 12 = x
0 = x

The simple problems your program is to solve are limited to integer values with multiplication, division, addition and subtraction operations. Note that, as in the above example, the computation must follow the standard order of precedence for arithmetic operations. All multiplications and divisions are performed, from left to right, before any additions and subtractions, and then all additions and subtractions are performed from left to right. You may assume that all divisions will result in integer values.

Input

The input file will consist of several equations to be solved. Each equation will contain from 1 to 20 operations with 2 to 21 integer operands (there will, of course, always be one more operand than operators). Integer operators in the input may have a leading sign (i.e. may be preceded by a unary operator). Spaces in the input line are optional; that is, spaces may be present between operators and operands, or they may not. The variable names will consist of 1 to 8 alphabetic characters.

Output

Output for a problem should begin with the problem to be solved, then followed by one line of output after each operation. The spacing between the numbers and operations in the output is not critical. Having the correct answers and all the correct steps in the output is important.

A typical input file will consist of multiple algebraic problems, each on a separate line. The output for each input problem should be separated by a single blank line in the output. The end of the file marks the end of the input.

Sample Input

3 * 4 + 4 - 1 / 1 = xyzzy
12 + 2 * 12 / 2 - 1 = y
2 * -3 + -6 - +4 = r
2*-3+-6-+4=r

Sample Output

3 * 4 + 4 - 1 / 1 = xyzzy
12 + 4 - 1 / 1 = xyzzy
12 + 4 - 1 = xyzzy
16 - 1 = xyzzy
15 = xyzzy

12 + 2 * 12 / 2 - 1 = y
12 + 24 / 2 - 1 = y
12 + 12 - 1 = y
24 - 1 = y
23 = y

2 * -3 + -6 - 4 = r
-6 + -6 - 4 = r
-12 - 4 = r
-16 = r

2 * -3 + -6 - 4 = r
-6 + -6 - 4 = r
-12 - 4 = r
-16 = r

---

#include <cstdio>
#include <cstring>
int main() {
    char s[1000];
    int i, j, first = 0;
    while(gets(s)) {
        if(first)   puts("");
        first = 1;
        int num[100], ope[100];
        int nt = 0, ot = 0, len = strlen(s);
        char *p;
        for(i = 0; i < len; i++) {
            while(s[i] == ' ')  i++;
            int tmp = 0;
            if(s[i] == '-') {
                i++;
                while(s[i] && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp*10 + s[i]-'0', i++;
                num[nt++] = -tmp;
            } else if(s[i] == '+') {
                i++;
                while(s[i] && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp*10 + s[i]-'0', i++;
                num[nt++] = tmp;
            } else {
                int tmp = 0;
                while(s[i] && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp*10 + s[i]-'0', i++;
                num[nt++] = tmp;
            }
            while(s[i] == ' ') i++;
            if(s[i] == '=') {
                i++;
                while(s[i] == ' ') i++;
                p = s+i;
                break;
            }
            ope[ot++] = s[i];
        }
        ope[nt-1] = '=';
        while(nt) {
            for(i = 0; i < nt; i++) {
                if(i)   putchar(' ');
                printf("%d %c", num[i], ope[i]);
            }
            putchar(' ');
            puts(p);
            int ok = 1;
            for(i = 0; i < ot; i++) {
                if(ope[i] == '*') {
                    num[i] = num[i]*num[i+1];
                    for(i++; i <= ot; i++)
                        num[i] = num[i+1], ope[i-1] = ope[i];
                    ok = 0;
                    break;
                }
                if(ope[i] == '/') {
                    num[i] = num[i]/num[i+1];
                    for(i++; i <= ot; i++)
                        num[i] = num[i+1], ope[i-1] = ope[i];
                    ok = 0;
                    break;
                }
            }
            if(ok) {
                if(ope[0] == '+')
                    num[0] = num[0]+num[1];
                if(ope[0] == '-')
                    num[0] = num[0]-num[1];
                for(i = 1; i <= ot; i++)
                    num[i] = num[i+1], ope[i-1] = ope[i];
            }
            ot--, nt--;
        }
    }
    return 0;
}