Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Алгоритмы > Реализация формул


Автор: osa 07.09.05, 09:53
Может тема должна называться чуть не так , но извенитею
и так подскажите пожалуйста как мне реализовать вычесление формулы , то есть например пользователь вводит ряд типа 2+5*(2+7) без никаких переменных и тд ...
Я понимаю что вопрос довольно грамосткия для ответа , поэтому ,если можно, дайте ссылку на статью

Автор: Relan 07.09.05, 11:26
Цитата osa @
пользователь вводит ряд типа 2+5*(2+7)
Причем тут ряд?
Поищи про алгоритм Рутисхаузера например (IMHO самый простой для реализации).

Автор: Swindler 07.09.05, 11:26
Выделение лексем, далее построение дерева, а затем - подсчет.

Автор: winny 08.09.05, 17:02
Это отлично организовывается с помощью бинарного дерева, если числа могут двух и более разрядными, и можно обойтись стеком, если числа могут быть только одноразрядными. Алгоритм хорошо описан в первом томе Д.Кнута.

Автор: Denny 08.09.05, 19:00
Или рекурсивно можно.

Автор: amk 09.09.05, 14:44
Рекурсивно проще и быстрее программу написать. Что-то типа:
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    double eval(char *str)
      {
      return expr(&str);
      }
     
    // Пропуск пробелов
    skipblanks(char **str)
      {
      while (**str == ' ') ++*str;
      }
     
    // Вычисление суммы
    double expr(char **str)
      {
      double value = prod(str);
      while (**str == '+' || **str == '-')
        {
        if (**str == '+' )
          {
          ++*str;
          value += prod(str);
          }
        else if (**str == '-')
          {
          ++*str;
          value -= prod(str);
          }
        }
      return value;
      }
     
    // Вычисление произведения
    double expr(char **str)
      {
      double value = prim(str);
      while (**str == '*' || **str == '/')
        {
        if (**str == '*' )
          {
          ++*str;
          value *= prim(str);
          }
        else if (**str == '/')
          {
          ++*str;
          value /= prim(str);
          }
        }
      }
     
    // Вычисление констант и выражений в скобках
    double prim(char **str)
      {
      if (isdigit(**str))
        {
        double value = *(*str)++ - '0';
        while (isdigit(**str))
          value = value * 10 + *(*str)++ - '0';
        return value;
        }
      if (**str == '(')
        {
        ++*str;
        double value = expr(str);
        if (**str == ')')
          ++*str
        else
          error();
        return value;
        }
      error();
      }
Вообще, такая задача рассматривается в любой книге посвященной трансляции. Просто в качестве примера. Я тут на память написал побыстрому. В выражении могут применяться знаки +, -, *, / и скобки. Числа в выражении могут быть только целыми. И я тут не фильтрую пробелы, которые могут встретиться в строке.

Автор: SexGenius 09.09.05, 16:11
На сайте sources.ru есть готовый пример с применением рекурсии. Очень понятный.

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)