【6342 HDU】Problem K. Expression in Memories（思维）

╰半夏微凉° 2022-05-17 04:50 106阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6342][http_acm.hdu.edu.cn_showproblem.php_pid_6342]

Sample Input：

5  
?????  
0+0+0  
?+\*??  
?0+?0  
?0+0?

Sample Output：

11111  
0+0+0  
IMPOSSIBLE  
10+10  
IMPOSSIBLE

题意：输入T代表测试样例，接下来输入T行字符串s（|s|≤ 500），每个字符串都是由“0、1、2、3、4、5、6、7、8、9、\*、+、？”组成的，每个字符串中的“？”都可以变成“0、1、2、3、4、5、6、7、8、9、\*、+”中的任意一个字符，从而组成一个有效表达式，如果能组成有效表达式，则输出此有效表达式，如果不能，则输出“IMPOSSIBLE”。

思路：这道题要注意我们不能直接用输入来判断字符串能否组成有效表达式，我们应该先把表达式求出来，然后再判断表达式是否符合条件。然后在我们求表达式的过程中，要注意要特判“+0？”（或“\*0？”）的情况，这种情况“？”要变成+，其他情况的“？”都可以变成1；最后就是判断表达式的时候，有3个条件，“+”和“\*”2个运算符不能连在一起、不能前导0、第一个字符和最后一个字符不能是运算符。

isdigit ( s )，s是char类型的字符，用来判断字符s是否是在“0~9”以内的数字字符，如果是就返回true（1），如果不是就返回false（0）。

My DaiMa：

//#include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int t;
        char s[1005];
        scanf("%d",&t);
        while( t-- )
        {
            scanf("%s",s);
            for( int i = 0; i < strlen(s); i++)
            {
                if(s[i] == '?')
                {
                    if(!isdigit(s[i-2]) && s[i-1] == '0' )//特判“+0？”和“*0？”的情况，此时？必须变成+
                        s[i] = '+';
                    else//其他的？都变成1
                        s[i] = '1';
                }
            }
            int flag = 0;
            for(int i = 0; i < strlen(s); i++)
            {
                if( !isdigit(s[i]) )//2个运算符“+”和“*”不能连在一起
                {
                    if( !isdigit(s[i+1]) )
                        flag = 1;
                }
    
                else if( s[i] == '0' )//当形为“运算符（+或*）0非零数字”时，不符合条件，即前导0
    
                {
                    if( !isdigit(s[i-1]) && isdigit(s[i+1]) )
                        flag = 1;
                }
            }
            if(!isdigit(s[0]) || !isdigit(s[strlen(s)-1]))//第一个和最后一个字符不能是运算符
                flag = 1;
            if(flag) printf("IMPOSSIBLE\n");
            else printf("%s\n",s);
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6342]: http://acm.hdu.edu.cn/showproblem.php?pid=6342