1

だから私はベクトルを再帰的に構築しようとしています.これを見ると、私はそれをかなり間違っていると思い始めます. 次のコードは、各反復の結果を含むベクトルを返しますか、それとも、各反復で実際には再帰呼び出しで構築されない新しいベクトルを作成するだけですか? 私が間違っている場合、再帰的にベクトルを作成するにはどうすればよいですか...建設的な助けをよろしくお願いします!

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

2 に答える 2

4

リスト (ベクターなど) を再帰的に作成する場合は、次のパターンを使用します。

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

あなたの場合、式が十分に長くなると、プログラムがスタックメモリを使い果たすため、スタックオーバーフロー例外が発生します。このアルゴリズムを線形に実装すると、それは起こりません。

于 2014-04-09T06:06:48.860 に答える
1

これを試してください。再帰呼び出しの結果を追加します

    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 のパターンを使用します。

于 2014-04-09T06:05:21.173 に答える