Problem K. Expression in Memories

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2150 Accepted Submission(s): 772
Special Judge

Problem Description

Kazari remembered that she had an expression

Input

The first line of the input contains an integer

Output

For each test case, print a string

Sample Input

?????

0+0+0

?+*??

?0+?0

?0+0?

Sample Output

11111

0+0+0

IMPOSSIBLE

10+10

IMPOSSIBLE

Source

2018 Multi-University Training Contest 4

题意概括：

给一串表达式（可能完整可能不完整），表达式只含有 ‘+’ 和 ‘ * ’ 两种运算，数字为 0~9；

如果不完整（含' ? ')，则补充完整。

若表达式本身非法或者无法补充成为一个合法表达式，则输出“IMPOSSIBLE”

解题思路：

很明显 “ ？” 只有在 0？的情况下需要变成 ‘+’ 或者‘*’; 其他情况都把 “ ？”变成非0的数字即可。

判断表达式是否合法：是否出现 0111 或者 ++ 或者 *+ 这类的情况即可。

AC code：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<set>
 9 #define INF 0x3f3f3f3f
10 #define LL long long
11 using namespace std;
12 const LL MOD = 1e9+7;
13 const int MAXN = 555;
14 char str[MAXN];
15 //char ans[MAXN];
16 
17 int main()
18 {
19     int T_case;
20     scanf("%d", &T_case);
21     while(T_case--){
22         scanf("%s", str);
23         int len = strlen(str);
24         bool flag = true;
25 
26         for(int i = 0; i < len; i++){
27             if(str[i] == '+' || str[i] == '*'){
28                 if(i == 0 || i == len-1){
29                     flag = false;
30                     break;
31                 }
32                 else if(str[i+1] == '+' || str[i+1] == '*'){
33                     flag = false;
34                     break;
35                 }
36             }
37             else if(str[i] == '0'){
38                 if(i == 0 || str[i-1] == '+' || str[i-1] == '*'){
39                     if(i < len-1 && str[i+1] >= '0' && str[i+1] <= '9'){
40                         flag = false;
41                         break;
42                     }
43                     else if(i < len-1 && str[i+1] == '?'){
44                         str[i+1] = '+';
45                     }
46                 }
47             }
48             else if(str[i] == '?'){
49                 str[i] = '1';
50             }
51         }
52 
53         if(flag) printf("%s
", str);
54         else puts("IMPOSSIBLE");
55     }
56     return 0;
57 }