Как сделать функцию O (n), которая проверяет наличие букв (верхний и нижний) & () + - * / в хвостовой рекурсии?

Question

Я пытаюсь выяснить, как преобразовать созданную мной функцию, которая проверяет переданную строку, если она содержит только буквы (строчные или прописные) и только эти знаки пунктуации () + - * / .... вэффективная рекурсивная функция, возможно, через хвостовую рекурсию.Вот мой код:

/*typedef std::string StringElem;*/
bool verify_input_str(StringElem str_para) {
  for (int x = 0; x < str_para.size(); ++x) {
    if (!(std::isalpha(str_para[x])) && (str_para[x] != '*')&& (str_para[x] != '/')
        && (str_para[x] != '+') && (str_para[x] != '-') && (str_para[x] != ')')
        && (str_para[x] != '(')) {
        return 0;
    }
  }
return 1;
}

Может кто-нибудь дать мне подсказку, я был бы очень признателен.Спасибо, с нетерпением ждем ваших предложений.

Answer 1

Поскольку хвостовая рекурсия требует, чтобы после рекурсивного вызова не производились вычисления, подход здесь довольно прост:

• Начните с подписи, которая включает текущую позицию pos в StringElement
• Сначала проверьте граничное условие; если строка пуста, вернуть успех
• Далее проверьте текущий символ; если он недействителен, вернуть ошибку
• Наконец, верните результат вызова самой функции с помощью pos+1.

Примечание: Я предполагаю, что вы работаете над обучением по хвостовой рекурсии, потому что в противном случае реализация на основе цикла была бы совершенно хорошим подходом.