logo标签列表

C++ - 如何从字符串中提取有效的子字符串？

c++stringparsingextract
3
问题：我正在尝试使用C++从游戏名称中提取Defense of the Ancients（DotA）的有效游戏模式。 细节：
  • 游戏名称最多可以为31个字符
  • 有三种游戏模式类别：主要、次要和杂项
    • 只能选择1个主要游戏模式
    • 某些主要游戏模式与某些次要游戏模式不兼容
    • 某些次要游戏模式与其他次要游戏模式不兼容
    • 杂项游戏模式可以与所有其他游戏模式组合使用

以下是各种游戏模式的列表，其中显示了每种模式与哪些次要模式兼容（X表示不兼容）：

// Only 1 primary allowed
static char *Primary[] = {
          // Compatible with > | dm | rv | mm | du | sh | aa | ai | as | id | em | np | sc | om | nt | nm | nb | ro | mo | sp | 
    "ap", // All Pick          |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "ar", // All Random        |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "tr", // Team Random       | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "mr", // Mode Random       | X  | X  |    |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "lm", // League Mode       | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |    |
    "rd", // Random Draft      | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "vr", // Vote Random       | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "el", // Extended League   | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |    |
    "sd", // Single Draft      | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "cm", // Captains Mode     | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |
    "cd"  // Captains Draft    | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
};

static char *Secondary[] = {
          // Compatible with > | dm | rv | mm | du | sh | aa | ai | as | id | em | np | sc | om | nt | nm | nb | ro | mo | sp | 
    "dm", // Death Match       |    | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "rv", // Reverse Mode      | X  |    |    |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "mm", // Mirror Match      | X  |    |    |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "du", // Duplicate Mode    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "sh", // Same Hero         | X  | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "aa", // All Agility       | X  |    |    |    |    |    | X  | X  |    |    |    |    |    |    |    |    |    |    |    |
    "ai", // All Intelligence  | X  |    |    |    |    | X  |    | X  |    |    |    |    |    |    |    |    |    |    |    |
    "as", // All Strength      | X  |    |    |    |    | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |
    "id", // Item Drop         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "em", // Easy Mode         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "np", // No Powerups       |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "sc", // Super Creeps      |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | 
    "om", // Only Mid          |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nt", // No Top            |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nm", // No Middle         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nb", // No Bottom         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | 
    "ro", // Range Only        | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | X  |    | 
    "mo", // Melee Only        | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | X  |    |    | 
    "sp"  // Shuffle Players   |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
};

// These options are always available
static char *Misc[] = {
    "ns", // No Swap
    "nr", // No Repick
    "ts", // Terrain Snow
    "pm", // Pooling Mode
    "oi", // Observer Info
    "mi", // Mini Heroes
    "fr", // Fast Respawn
    "so"  // Switch On
};

示例：这里有一些输入的示例，以及期望的输出：

"DotA v6.60 -RDSOSP USA/CA LC!" -> "rdsosp"

"DOTA AREMDM USA LC" -> "aremdm"

"DotA v6.60 -ApEmDuSpId USA BL" -> "apemduspid"

注意：解决方案不一定要提供实际代码，伪代码甚至只是解释如何处理都可以接受和优先考虑。此外，解决方案需要足够灵活，以便我能够轻松地添加另一个游戏模式。还可以安全地假设，在游戏名称中，游戏模式将始终从主要游戏模式开始。

结果：

#include <cstdarg>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <vector>

std::map<std::string, std::vector<std::string> > ModeCompatibilityMap;

static const unsigned int PrimaryModesCount = 11;
static char *PrimaryModes[] = { 
    "ap", "ar", "tr", "mr", "lm", "rd", "vr", "el", "sd", "cm", "cd"
};

static const unsigned int SecondaryModesCounts = 19;
static char *SecondaryModes[] = {
    "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np",
    "sc", "om", "nt", "nm", "nb", "ro", "mo", "sp"
};

static const unsigned int MiscModesCount = 8;
static char *MiscModes[] = {
    "ns", "nr", "ts", "pm", "oi", "mi", "fr", "so" 
};

std::vector<std::string> Vectorize( int count, ... ) {
    std::vector<std::string> result;

    va_list vl;
    va_start( vl, count );

    for ( int i = 0; i < count; ++i ) {
        char *buffer = va_arg( vl, char * );
        result.push_back( buffer );
    }

    va_end( vl );

    return result;
}

void InitializeModeCompatibilityMap() {
    // Primary
    ModeCompatibilityMap["ar"] = Vectorize( 1, "rv" );
    ModeCompatibilityMap["tr"] = Vectorize( 2, "dm", "rv" );
    ModeCompatibilityMap["mr"] = Vectorize( 8, "dm", "rv", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["lm"] = Vectorize( 18, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo" );
    ModeCompatibilityMap["rd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["vr"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["el"] = Vectorize( 18, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo" );
    ModeCompatibilityMap["sd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["cm"] = Vectorize( 19, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo", "sp" );
    ModeCompatibilityMap["cd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );   
    // Secondary
    ModeCompatibilityMap["dm"] = Vectorize( 8, "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["rv"] = Vectorize( 2, "dm", "sh" );
    ModeCompatibilityMap["mm"] = Vectorize( 2, "dm", "sh" );
    ModeCompatibilityMap["sh"] = Vectorize( 3, "dm", "rv", "mm" );
    ModeCompatibilityMap["aa"] = Vectorize( 3, "dm", "ai", "as" );
    ModeCompatibilityMap["ai"] = Vectorize( 3, "dm", "aa", "as" );
    ModeCompatibilityMap["as"] = Vectorize( 3, "dm", "aa", "ai" );
    ModeCompatibilityMap["ro"] = Vectorize( 2, "dm", "mo" );
    ModeCompatibilityMap["mo"] = Vectorize( 2, "dm", "ro" );
}

std::vector<std::string> Tokenize( const std::string &string ) {
    std::vector<std::string> tokens;
    std::string token;
    std::stringstream ss( string );

    while ( ss >> token ) {
        tokens.push_back( token );
    }

    return tokens;
}

void SanitizeString( std::string &in ) {
    std::transform( in.begin(), in.end(), in.begin(), tolower );

    for ( size_t i = 0; i < in.size(); ++i ) {
        if ( in[i] < 'a' || in[i] > 'z' ) {
            in.erase( i--, 1 );
        }
    }
}

std::vector<std::string> SplitString( const std::string &in, int count ) {
    std::vector<std::string> result;

    if ( in.length() % count != 0 ) {
        return result;
    }

    for ( std::string::const_iterator i = in.begin(); i != in.end(); i += count ) {
        result.push_back( std::string( i, i + count ) );
    }

    return result;
}

bool IsPrimaryGameMode( const std::string &in ) {
    for ( int i = 0; i < PrimaryModesCount; ++i ) {
        if ( strcmp( PrimaryModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsSecondaryGameMode( const std::string &in ) {
    for ( int i = 0; i < SecondaryModesCounts; ++i ) {
        if ( strcmp( SecondaryModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsMiscGameMode( const std::string &in ) {
    for ( int i = 0; i < MiscModesCount; ++i ) {
        if ( strcmp( MiscModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsValidGameMode( std::string in, std::string &out ) {
    // 1. Strip all non-letters from the string and convert it to lower-case
    SanitizeString( in );

    // 2. Confirm that it is a multiple of 2
    if ( in.length() == 0 || in.length() % 2 != 0 ) {
        return false;
    }

    // 3. Split the string further into strings of 2 characters
    std::vector<std::string> modes = SplitString( in, 2 );

    // 4. Verify that each game mode is a valid game mode and is compatible with the others
    bool primaryModeSet = false;

    for ( size_t i = 0; i < modes.size(); ++i ) {
        if ( IsPrimaryGameMode( modes[i] ) || IsSecondaryGameMode( modes[i] ) ) {
            if ( IsPrimaryGameMode( modes[i] ) ) {
                if ( primaryModeSet ) {
                    return false;
                }

                primaryModeSet = true;
            }

            if ( ModeCompatibilityMap.count( modes[i] ) > 0 ) {
                std::vector<std::string> badModes = ModeCompatibilityMap[modes[i]];

                for ( size_t j = 0; j < badModes.size(); ++j ) {
                    for ( size_t k = 0; k < modes.size(); ++k ) {
                        if ( badModes[j] == modes[k] ) {
                            return false;
                        }
                    }
                }
            }
        } else if ( !IsMiscGameMode( modes[i] ) ) {
            return false;
        }
    }

    // 5. Assign the output variable with the game mode and return true
    out = in;

    return true;
}

std::string ExtractGameMode( const std::string &gameName ) {
    std::vector<std::string> tokens = Tokenize( gameName );

    std::string gameMode;

    for ( size_t i = 0; i < tokens.size(); ++i ) {
        if ( IsValidGameMode( tokens[i], gameMode ) ) {
            return gameMode;
        }
    }

    return "";
}

int main( int argc, char *argv[] ) {
    InitializeModeCompatibilityMap();

    std::string gameName = "DotA v6.60 -RDEM USA/CA LC";
    std::string gameMode = ExtractGameMode( gameName );

    std::cout << "Name: " << gameName << std::endl;
    std::cout << "Mode: " << gameMode << std::endl;

    return 0;
}

输出:

名称: DotA v6.60 -RDEM USA/CA LC

模式: rdem

如果有人想审查此代码并告诉我他们会改变什么，那将不胜感激。

谢谢。

我不太明白，您需要做什么：1. 从游戏名称中提取游戏模式。2. 验证它们是否相互兼容？ - Idan K
4个回答
2

创建布尔数组，复制您放入注释中的表格。但不要使用“X”或空白，而是使用“true”或“false”（因此，“true”表示模式组合有效，“false”表示无效）。

使用此表查找组合是否有效：

 bool IsSecondaryValidWithPrimary(unsigned int primaryIndex, unsigned int secondaryIndex)
 {
     static bool secondaryValidWithPrimary[numPrimaryModes][numSecondaryModes] = {...}

     if (primaryIndex < numPrimaryModes && secondaryIndex < numSecondaryModes)
     {
         return secondaryValidWithPrimary[primaryIndex][secondaryIndex]
     }
     else
     {
         //... this should never happen, throw your favorite exception
     }
 }

自然，这要求您将每个2个字符的字符串转换为正确的数组索引以进行测试。循环遍历每个可能的组合并检查其是否有效。我怀疑您在这种设置中严肃关注性能，因此这应该可以很好地工作。
对于另一个有效性检查（与另一个次要检查相同）或任何其他模式的组合，都需要执行相同的操作，并根据兼容性规则进行检查。
1
从主机游戏名称中提取游戏类型将很难，除非有更多的规则。如果您真的想避免给最终用户更多的规则，可以尝试以下方法...
  • 将整个游戏名称字符串转换为小写。
  • 使用空格' '分隔符拆分游戏名称。
  • 分析每个单词，执行以下操作。如果出现任何错误，请转到下一个单词。
  • 取出[0]并确定它是否具有97-122的ASCII值（确保它是一个字母）。如果不在这些值内，则继续下一个字符，直到它符合条件（显然不超过数组边界）。这将删除任何用户格式，如连字符-apem。
  • 使用strcmp()将下两个字符与每个主要游戏类型进行比较，直到找到匹配项。否则失败并移动到下一个单词。
  • 对于剩余的字符，使用strcmp()将每个下一对字符与每个次要或杂项游戏类型进行比较。如果有任何不匹配的情况，请退出到下一个单词，或者如果只剩下1个字符，请退出到下一个单词

这样就可以提取游戏类型，或者您可以责怪用户使用了错误的游戏名称。

现在是更难的部分，验证游戏类型是否彼此兼容。我建议您创建一个结构体，其中包含表示每个次要游戏类型的布尔值数据结构。可以使用std::map或单个布尔数组，该数组可以使用枚举访问。

现在，您需要一个数据对象来表示每个主要游戏类型以及每个次要游戏类型。

然后，只需创建一个包含所有游戏类型（包括主要和次要）的数组。请参考代码示例：

map<const char*, bool> mapSecondaryCompatibility;

struct tGameType
{
    char szName[3];
    mapSecondaryCompatibility m_compat;
}

正如您所看到的，从技术上讲，您的主要游戏类型和次要游戏类型之间并没有区别，它们都有相同的限制...可能与另一个次要游戏类型不兼容。

通过这个，我相信您可以想出其余部分。希望能对您有所帮助，我得回去工作了 :)

哦，我是 DotA 的忠实粉丝...继续保持好工作！

这实际上相当接近我最终所做的事情，因此我将接受这个答案，并使用我的代码编辑我的帖子。 - xian
1

我可能会尝试将每个模式放入一个std::set中，并带有与给定节点兼容的模式的白名单。当您想要解析模式字符串时，您需要复制主要白名单。然后，您通过字符串向下步进。如果下一个节点不在白名单中，则您有一个无效的模式字符串。如果下一个模式在白名单中，则将下一个节点的白名单与您的工作白名单相交。继续直到到达字符串的末尾或白名单为空。如果白名单为空且未到达字符串的末尾，则它是无效的，否则它是好的。

杂项模式可能不属于白名单（因为它们在每个白名单上）。

您还可以尝试使用黑名单，并在每个步骤中创建联合，然后在列表中退出模式。

0

我倾向于将游戏模式类型转换为枚举。甚至可以将模式包装在一个类中，该类可以存储当前游戏模式状态，并为游戏的其他部分提供友好的访问器，以便快速查询当前模式。

在内部，我会创建一个std::map>来存储兼容模式的列表。一旦输入命令行，我会将两个字符字符串转换为枚举值。然后，我会在兼容模式映射中进行查找，看它是否是允许的模式。

如何填充映射取决于您 - 我认为您可以有一个负责此操作的类 - 一个兼容性加载器，或者如果您希望最终用户能够修改可用模式，也可以从配置文件驱动它。

使用枚举更方便，因为您可以在编译时进行大量检查，而不是运行时检查。当您从输入字符串转换为枚举时，只需进行一次运行时检查，如果无效，则向用户返回失败消息。然后，所有其他代码都在编译时进行检查。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接