算法标签

• 字符串处理：主要涉及字符串的解析和验证
• 进制转换：处理不同进制数字的合法性检查
• 递归：用于处理嵌套的整数常量格式

解题思路

1. 输入处理：

   • 首先读取整数$n$，表示需要验证的字符串数量
   • 然后逐行读取$n$个字符串进行验证

2. 验证函数isValidIntegerConstant：

   • 基数检测：检查字符串是否包含#符号来确定是否有显式指定的基数
   • 基数验证：
     • 提取#前的部分作为基数
     • 验证基数是否全为数字且在$2$到$16$的范围内
   • 数字部分验证：
     • 对于有基数的形式，验证#...#之间的字符是否都是该基数的有效数字
     • 对于十进制形式，验证是否全为数字字符
   • 递归处理：允许类似2#101##123#这样的嵌套格式

3. 辅助函数isDigit：

   • 根据给定的基数验证字符是否为该基数的有效数字
   • 处理$10$以上进制时，接受字母a-f表示$10-15$

4. 输出结果：

   • 对每个字符串调用验证函数
   • 根据验证结果输出yes或no

#include <iostream>
#include <string>
#include <cctype>
#include <cstdlib> // for atoi 
using namespace std;
 
bool isDigit(char c, int base) {
    if (base <= 10) {
        return isdigit(c) && (c - '0') < base;
    } else {
        return isdigit(c) || (tolower(c) >= 'a' && tolower(c) <= 'f' && (tolower(c) - 'a' + 10) < base);
    }
}
 
bool isValidIntegerConstant(const string &s) {
    size_t pos = 0;
    int base = 10;
    bool hasBase = false;
 
    // Check for base part 
    size_t firstHash = s.find('#'); 
    if (firstHash != string::npos) {
        string baseStr = s.substr(0,  firstHash);
        
        // Parse base 
        if (baseStr.empty())  return false;
        for (size_t i = 0; i < baseStr.size();  ++i) {
            char c = baseStr[i];
            if (!isdigit(c)) return false;
        }
        base = atoi(baseStr.c_str());
        if (base < 2 || base > 16) return false;
        
        pos = firstHash + 1;
        hasBase = true;
    }
 
    // Check for digits part 
    if (pos >= s.size())  return false;
    size_t endHash = s.find('#',  pos);
    if (hasBase) {
        if (endHash == string::npos) return false;
        string digits = s.substr(pos,  endHash - pos);
        if (digits.empty())  return false;
        for (size_t i = 0; i < digits.size();  ++i) {
            char c = digits[i];
            if (!isDigit(c, base)) return false;
        }
        pos = endHash + 1;
    } else {
        // Decimal case 
        string digits = s.substr(pos); 
        if (digits.empty())  return false;
        for (size_t i = 0; i < digits.size();  ++i) {
            char c = digits[i];
            if (!isdigit(c)) return false;
        }
        return true;
    }
 
    // Check if there's anything after the last #
    if (pos < s.size())  {
        string remaining = s.substr(pos); 
        if (remaining.empty())  return true;
        // Check if the remaining is a valid integer constant 
        return isValidIntegerConstant(remaining);
    }
 
    return true;
}
 
int main() {
    int n;
    cin >> n;
    cin.ignore();  // Ignore the newline after n 
    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s);
        if (isValidIntegerConstant(s)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}