ZOJ Problem Set - 3325
Sempr is looking for a girlfriend now. On his way of seeking a beauty, he met many difficult problems. Here is one of them.
In order to judge whether an expression can be equal to some value, he has to enumerate the calculation order of the operators. So he changes the expression without parentheses into a regular expression. The regular expression is defined as follows:
O ::= "+" | "-" | "*" | "/"
N ::= [0-9]+
The regular expression is unambiguous and its calculation order is defined. For example, ((1+2)-(3*4)) is a regular expression. We can first evaluate (1+2) and get 3. Then we evaluate (3*4) and get 12. At last, we evaluate (3-12) and get -9. Note the evaluations are performed from left to right.
Of course, Sempr is so powerful that he can write a program to evaluate a regular expression easily. But enumerating the regular expressions of an expression is a bit difficult for him. So he asks you for help. Your job is to find the smallest regular expression that is larger than the given one in lexicographic order.
A regular expression is lexicographically smaller than another regular expression of the same expression iff the last operator to evaluate that differs between the two regular expressions in the first regular expression is after that in the second regular expression. For example, the evaluation order of regular expression (((6+7)+8)+9) is 1, 2, 3. The evaluation order of ((6+(7+8))+9) is 2, 1, 3. The second operators of them, which are the last operands that differ between them, are 2 and 1. The first one is after the second one. Hence, the first expression is lexicographically smaller than the second one.
The first line of the input contains an integer T (T <= 100), indicating the number of cases.
Each test case contains one line of the expression that is only made up of parentheses ("(", ")"), digits ("0"-"9") and operators ("+", "-", "*", "/"). The length of the expression will be between 1 and 1,000,000, inclusive.
If the given expression is not a regular expression, output "Error". If the expression has no lexicographically larger regular expression, output "-1". Otherwise, output the smallest regular expression that is larger than the given one. NOTE that you need NEITHER to evaluate whether the expression is valid, NOR to omit the leading zeros in the expression that are not needed.
4 1+1 (1+1) ((1+2)*3) ((12+3)/(0+3))
Error -1 (1+(2*3)) (12+((3/0)+3))
Author: GUAN, Yao
Source: The 7th Zhejiang Provincial Collegiate Programming Contest