c - 排列基本 BNF 样式字符串

Question

我想找到非常简单的类似 BNF 风格的字符串的所有排列。

唯一的运算符是()[]|

so () 表示“必须有” [] 表示“可选”，| 表示“或”

给定一个字符串(foo | bar) [zop] [flip |失败]

它会给我以下结果:

• foo 翻转
• foo zop 翻转
• foo zop 失败
• foo 失败
• 条形翻转
• 酒吧快速翻转
• 酒吧 zop 翻牌
• 酒吧翻牌
• foo 佐普
• 酒吧佐普
• 富
• 酒吧

我可以使用任何算法来做到这一点吗？我可以编写一个简单的解析器+分词器，但我的直觉是可能有一个更简单的解决方案。我正在 ISO C 中对其进行编码。

Answer 1

您可以做的是使用递归进行字符串解析。因此对于每个角色:

1. 如果以“[”开头，则处理强制设置
2. 如果以“(”开头，则处理可选集
3. 否则直接跳转到下一个右括号“)”或“]”

处理强制和可选集是获取其标记并迭代它们并重复上面的 3 个步骤。另外，处理可选集有一个空迭代，不包含任何东西作为其可选。所以:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1024

void printPermutation(char* result[], int size) {
        for (int i = 0; i < size; ++i) {
                printf("%s ", result[i]);
        }
        printf("\n");
}

void parseDeep(char* s, char* result[], int currIdx) {
    char* mandatory[1024];
    char* optional[1024];
    char *start = 0, *end = 0;
    char* delim = "|";
    int mandatorySize = 0;
    int optionalSize = 0;

    while (*s != 0) {
            //Mandatory
            if ('(' == *s) {
                ++s;
                end = start = s;
                while (*end != ')') {
                        ++end;
                }
                char* mandatorySet = malloc(end - start + 1);
                strncpy(mandatorySet, start, end - start);
                mandatorySet[end - start] = 0;

                char* token = strtok(mandatorySet, delim);
                while (token != 0) {
                        mandatory[mandatorySize] = malloc(strlen(token) + 1);
                        strcpy(mandatory[mandatorySize++], token);
                        token = strtok(0, delim);
                }
                for (int m = 0; m < mandatorySize; ++m) {
                        result[currIdx] = mandatory[m];
                        parseDeep(end, result, currIdx + 1);
                }
                for (int i=0; i < mandatorySize; ++i) {
                    free(mandatory[i]);
                }
                free(mandatorySet);
                s = end;
                return;
            //Optional
            } else if ('[' == *s) {
                ++s;
                end = start = s;
                while (*end != ']') {
                        ++end;
                }
                char* optionalSet = malloc(end - start + 1);
                strncpy(optionalSet, start, end - start);
                optionalSet[end - start] = 0;

                char* token = strtok(optionalSet, delim);
                while (token != 0) {
                        optional[optionalSize] = malloc(strlen(token) + 1);
                        strcpy(optional[optionalSize++], token);
                        token = strtok(0, delim);
                }
                for (int m = -1; m < optionalSize; ++m) {
                        //Optional when it is not added
                        if (m == -1) {
                            continue;
                        } else {
                            result[currIdx] = optional[m];
                            parseDeep(end, result, currIdx + 1);
                        }

                }
                for (int i=0; i < optionalSize; ++i) {
                    free(optional[i]);
                }
                free(optionalSet);
                s = end;
            }
            mandatorySize = optionalSize = 0;
            ++s;
        }
    printPermutation(result, currIdx);
}

void parse(char* s) {
        char* result[MAX_SIZE];
        parseDeep(s, result, 0);
}


int main() {
    char *s = "(foo | bar) [zop] [flip | flop]";
    parse(s);
}

这不会检查字符串的有效性。