Description

Red cape flying cat wrote a small calculator. The calculator can process expressions containing non-negative integers, +, -, *, and parentheses.

However, his calculator does not understand the custom operators @ and $. Before giving an expression to the calculator, you need to replace every custom operator with an equivalent expression using only ordinary operators.

Definition

The custom operators are defined as:

a @ b = a - (a * b) + b
a $ b = (a @ b)

Therefore:

a $ b = (a - (a * b) + b)

Here, a and b are both factors.

In this problem, a factor is:

FACTOR = NUMBER | (EXPR)

That is, a factor is either a non-negative integer or a parenthesized expression.

For each custom operator, its left operand is the nearest valid factor immediately on its left, and its right operand is the nearest valid factor immediately on its right.

Replacement Rule

You must repeatedly perform the following operation:

1. Find the leftmost custom operator, either @ or $, in the current expression.
2. Let a be the nearest factor on its left.
3. Let b be the nearest factor on its right.
4. If the operator is @, replace a@b with a-(a*b)+b.
5. If the operator is $, replace a$b with (a-(a*b)+b).

After a replacement, the new expression becomes the current expression. Continue until there is no custom operator left.

The final expression must contain only digits, +, -, *, (, and ). Do not output spaces.

Examples

For:

2@3

The result is:

2-(2*3)+3

For:

2$3

The result is:

(2-(2*3)+3)

For:

(2+3)@4

The left factor is (2+3), and the right factor is 4, so the result is:

(2+3)-((2+3)*4)+4

For:

2*3@4

The left factor of @ is only 3, not 2*3. Therefore, the result is:

2*3-(3*4)+4

For multiple custom operators, always replace the leftmost one first:

2@3$4
=> 2-(2*3)+3$4
=> 2-(2*3)+(3-(3*4)+4)

Partial Judge

This is a partial judge problem. The judge provides main.c and function.h.

You only need to implement:

void replace_custom_operator(char expr[], char result[]);

expr is the original expression. You should store the final expression in result. The judge will print result.

The provided function.h also contains suggested helper function names used by the reference solution. You do not have to use exactly those helper functions, but they may help you split the implementation into smaller parts.

Input

The input is read by the judge's main.c.

The input contains one line: a valid expression expr.

Constraints

1 <= |expr| <= 2000
0 <= NUMBER <= 1000000000
After replacing all custom operators, the expression length will not exceed 50000.

• The expression contains only digits, +, -, *, @, $, (, and ).
• The expression is valid.
• There are no spaces in the expression.
• Unary minus will not appear in the input.

Output

The output is produced by the judge's main.c.

Output the expression after replacing all custom operators.

The output should not contain spaces.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14942.c

Partial Judge Header

14942.h

Discuss