Оценить выражение в строке рекурсивно

Question

Допустим, мы хотели бы оценить выражения в строке.Выражения, представленные (###) для простоты в примере.Мы только посчитали хэштеги в примере для простоты.Выражения могут быть вложенными.

#include <iostream>
#include <string>

std::string expression{ "(###(##)#(###)##)" };

int countHash(std::string::iterator stringIterator, std::string::iterator stringEnd)
{
    int result = 0;
    while (stringIterator != stringEnd)
    {
        if (*stringIterator == '#')
        {
            result += 1;
        }
        else if (*stringIterator == '(')
        {
            result += countHash(++stringIterator, stringEnd);
        }
        else if (*stringIterator == ')')
        {
            return result += countHash(++stringIterator, stringEnd);
        }
        ++stringIterator;
    }
    return result;
}

int main()
{
    std::cout << countHash(expression.begin(), expression.end()) << std::endl;
    return 0;
}

Вывод: 51

Ожидаемый вывод: 11

Так что моя проблема в том, когдаЯ возвращаюсь из рекурсивного вызова, итератор не обновляется.Это позади.Обработка проходит через части строки несколько раз.Как мне справиться с этим?

Кстати, моя главная цель - уметь оценивать такие выражения:

std::string expr = "(+1 (+22 3 25) 5 (+44 (*3 2)))";
EXPECT(106== evalExpression(expr.begin(), expr.end()));

Спасибо.

РЕДАКТИРОВАТЬ:

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

Answer 1

ОК, так как я редактировал свой оригинальный вопрос, вот решение для этого:

#include <iostream>
#include <string>

std::string expression{ "(###((##)#)(#(#)#)#(#))" };

int countHash(std::string::iterator& stringIterator, std::string::iterator stringEnd)
{
    int result = 0;
    while (stringIterator != stringEnd)
    {
        if (*stringIterator == '#')
        {
            result += 1;
        }
        else if (*stringIterator == '(')
        {
            result += countHash(++stringIterator, stringEnd);
            continue;
        }
        else if (*stringIterator == ')')
        {
            ++stringIterator;
            return result;
        }
        ++stringIterator;
    }
    return result;
}

int countHash(std::string expression)
{
    auto it = expression.begin();
    return countHash(it, expression.end());
}

int main()
{
    std::cout << countHash(expression) << std::endl;
    return 0;
}

Вывод: 11

Итак, одна важная вещь заключалась в том, что вынеобходимо передать строку по ссылке, чтобы избежать повторной обработки одних и тех же сегментов строки после возврата из рекурсивных вызовов.

С чем я также столкнулся, так это с тем, что вам нужно сделать continue послерекурсивный вызов в моем цикле while.Это потому, что вы не хотите увеличивать stringIterator после возврата из рекурсивного вызова.Вы также можете сделать это с помощью оператора постинкремента и с помощью switch-case, как это сделал @bruno в своем ответе.Это было понимание для меня.Если вы проверяете не только символы switch-case, это невозможно.Вы можете использовать цикл do-while, но мне это не нравится.

Еще более важным было то, что вам нужно увеличить свой итератор перед возвращением из ветви ).Это потому, что это конец выражения, и если это был рекурсивный вызов, вы хотите продолжить выражение на стороне вызывающей стороны.

Еще одна проблема заключалась в том, что вы не можете передать expression.begin(), если ваша функция принимаетссылка на итератор.

Для выражения

std::string expr = "(+1 (+22 3 25) 5 (+44 (*3 2)))";

мое решение доступно на https://github.com/bencemeszaroshu/expeval/blob/master/expeval/expeval.cpp. Мне не нравится, как сейчас, но я постараюсь улучшитьэто позже.(Рад слышать предложения.) Однако это работает.Спасибо всем за вашу помощь, я отмечаю ответ @bruno как принятый, потому что он помог мне больше всего.

Answer 2

#include <string>
#include <iostream>

std::string expression{ "#####-###-##" };

int countHash(std::string::iterator & stringIterator, std::string::iterator stringEnd)
{
  int result = 0;
  while (stringIterator != stringEnd)
  {
    switch (*stringIterator++)
    {
    case '#':
      result += 1;
      break;
    case '-':
      result += countHash(stringIterator, stringEnd);
      break;
    default:
      // indicate error ?
      break;
    }
  }
  return result;
}

int main()
{
  std::string::iterator b = expression.begin();
  std::cout << countHash(b, expression.end()) << std::endl;
  return 0;
}