Рекурсивная функция построения вектора, что будет возвращено?

Question

Рекурсивная функция построения вектора, что будет возвращено?

поэтому я пытаюсь рекурсивно построить вектор, когда я смотрю на это, я начинаю думать, что делаю это совершенно неправильно. Будет ли следующий код возвращать вектор с результатами каждой итерации, или я просто создаю новые векторы на каждой итерации, которые фактически не будут основываться на каждом рекурсивном вызове. Если я не прав, как мне рекурсивно строить вектор … Заранее спасибо за вашу конструктивную помощь!

std::vector<ParameterClass> recursiveParser :: parseParamList()
{
std::vector<ParameterClass> paramVector;

if (lexicator->getCurrentToken()->getTokenType() == STRING) {

paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
lexicator->advance();
parseParamList();

} else if (lexicator->getCurrentToken()->getTokenType() == ID) {

paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
lexicator->advance();
parseParamList();

} else {

// so as to not fail in Expression, i need to check to see that there is a
// left paren indicating that there should be an expression

if (lexicator->getCurrentToken()->getTokenType() == LEFT_PAREN) {
paramVector.push_back(ParameterClass(parseExpression()));
lexicator->advance();
parseParamList();
}
}
return paramVector;
}

1

c++construction recursion vector

Решение

Другие решения

попробуйте это, чтобы добавить результат от рекурсивного вызова

    std::vector<ParameterClass> recursiveParser :: parseParamList()
{
std::vector<ParameterClass> paramVector;
if(lexicator->getCurrentToken()->getTokenType() == STRING)
{
paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
lexicator->advance();
std::vector<ParameterClass> result = parseParamList();
std::copy(result.begin(), result.end(), std::back_inserter(paramVector));
}
else
if(lexicator->getCurrentToken()->getTokenType() == ID)
{
paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
lexicator->advance();
std::vector<ParameterClass> result = parseParamList();
std::copy(result.begin(), result.end(), std::back_inserter(paramVector));
}else
{
// so as to not fail in Expression, i need to check to see that there is a left paren indicating that there should be an expression
if(lexicator->getCurrentToken()->getTokenType() == LEFT_PAREN)
{
paramVector.push_back(ParameterClass(parseExpression()));
lexicator->advance();
std::vector<ParameterClass> result = parseParamList();
std::copy(result.begin(), result.end(), std::back_inserter(paramVector));
}
}
return paramVector;
}

Также, пожалуйста, используйте переключатель вместо if-elseif-elseif и избежать повторного кода

std::vector<ParameterClass> recursiveParser :: parseParamList()
{
std::vector<ParameterClass> paramVector;

switch(lexicator->getCurrentToken()->getTokenType())
{
case STRING:
paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
break;
case ID:
paramVector.push_back(ParameterClass(*lexicator->getCurrentToken()));
break;
case LEFT_PAREN: // so as to not fail in Expression, i need to check to see that there is a left paren indicating that there should be an expression
paramVector.push_back(ParameterClass(parseExpression()));
break;
}
lexicator->advance();
std::vector<ParameterClass> result = parseParamList();
std::copy(result.begin(), result.end(), std::back_inserter(paramVector));
return paramVector;
}

но используйте шаблон @ Spook, потому что он позволяет оптимизировать хвостовой вызов

1

Источник

Accepted Answer

Если вы хотите построить список (вектор и т. Д.) Рекурсивно, используйте следующий шаблон:

private:
void InternalBuild(std::vector<OutputData> & vec)
{
// Add data to vec
// Possibly call recursively InternalBuild(vec);
}

public:
std::vector<OutputData> RecursiveBuild()
{
std::vector<OutputData> vec;
InternalBuild(vec);
return vec;
}

Стоит отметить, что вы, кажется, неправильно используете рекурсию здесь. Рекурсия предназначена для использования в структурах данных, которые по своей природе являются рекурсивными (деревья, графики и т. Д.). В этом случае вы обрабатываете линейные данные рекурсивно — почему бы просто не написать что-то вроде:

while (!lexer.endOfExpression())
{
// Process token

lexer.Advance();
}

В вашем случае, если вы получите выражение достаточно длинное, вы получите исключение переполнения стека, потому что вашей программе не хватит памяти стека. Этого не произойдет, если вы реализуете этот алгоритм линейно.

4