Блог

Я хочу найти все перестановки для очень простых строк в стиле, похожем на BNF.

Единственными операторами являются ()[]|

итак, () вместо «должен иметь» [] «необязательно» и | вместо «или»

Итак, задана строка (foo | bar) [zop] [flip | flop]

Это дало бы мне следующий результат:

• foo flip
• foo zop flip
• foo zop flop
• сбой foo
• переворот строки
• переворот строки zop
• барный зоп-флоп
• бар-флоп
• foo zop
• строка zop
• foo
• строка

Существуют ли какие-либо алгоритмы, которые я могу использовать для этого? Я могу написать простой синтаксический анализатор токенизатор, но я нутром чувствую, что, вероятно, есть более простое решение. Я кодирую это в ISO C.

Что вы можете сделать, так это использовать рекурсию при синтаксическом анализе строки. Итак, для каждого символа:

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);
}
  

Это не проверяет правильность строки.