воскресенье, 10 апреля 2011 г.

Вычисление выражения из строки

   Попалась интересная задача. Суть в следующем: есть выражение в виде строки что-то вроде "5*(-1)/2.5+2*2+(+1-3.0)". Нужно получить ответ. Естественно, программа должна быть готова к любому выражению. Чтобы не слишком усложнять задачу, будем считать, что выражение всегда корректно. То есть "5*" введено в программу не будет. Сложность в другом (на самом деле одновременно и подсказка). Нужно, чтобы приложение было абсолютно расширяемым. Сюда относится: возможность быстро добавить новую операцию (остаток от деления, например), возможность изменить саму операцию, не изменяя ее отображения ("хочу, чтобы + делил, а / складывал").


   Что ж приступим. Для начала следует описать доменную модель. У нас есть такие понятия как "выражение" и "операция". Опишем эти сущности в виде интерфейсов:

  1. namespace CalculateExpressions.Domain
  2. {
  3.   public interface IExpression
  4.   {
  5.     double Result();
  6.   }
  7. }
* This source code was highlighted with Source Code Highlighter.

  1. namespace CalculateExpressions.Domain
  2. {
  3.   public interface IOperation
  4.   {
  5.     IExpression Calculate();
  6.   }
  7. }
* This source code was highlighted with Source Code Highlighter.
   Да, будем пока опираться на то, что выражение просто имеет какой-то результат. Операция просто возвращает какое-то выражение методом Calculate (возможно название не совсем корректно, ничего лучше в голову не пришло). Пора заняться операциями. Нам известно, что операции можно разделить на несколько категорий: унарные, бинарные и с б`ольшим количеством параметров.

  1. namespace CalculateExpressions.Domain
  2. {
  3.   public abstract class UnaryOperation: IOperation
  4.   {
  5.     public IExpression Parameter { get; protected set; }
  6.  
  7.     protected UnaryOperation(IExpression param)
  8.     {
  9.       Parameter = param;
  10.     }
  11.  
  12.     #region IOperation Members
  13.  
  14.     public abstract IExpression Calculate();
  15.  
  16.     #endregion
  17.   }
  18. }
* This source code was highlighted with Source Code Highlighter.

  1. namespace CalculateExpressions.Domain
  2. {
  3.   public abstract class BinaryOperation: IOperation
  4.   {
  5.     public IExpression Parameter1 { get; protected set; }
  6.  
  7.     public IExpression Parameter2 { get; protected set; }
  8.  
  9.     protected BinaryOperation(IExpression param1, IExpression param2)
  10.     {
  11.       Parameter1 = param1;
  12.       Parameter2 = param2;
  13.     }
  14.  
  15.     #region IOperation Members
  16.  
  17.     public abstract IExpression Calculate();
  18.  
  19.     #endregion
  20.   }
  21. }
* This source code was highlighted with Source Code Highlighter.
  Некоторым может показаться, почему бы в унарной операции в методе Calculate просто не возвращать параметр конструкции. Но смысл унарной операции ведь в том и состоит, чтобы одно выражение превратить в другое. Поэтому входящее выражение нельзя путать с полученным.
  Насчет выражений. Его задача просто выдать результат. Если выражение состоит из операции и ее операндов, то будем считать его вычисляемым. Вычисляемое выражение будет содержать в себе эту операцию и при помощи нее получать результат.

  1. using CalculateExpressions.Domain;
  2.  
  3. namespace CalculateExpressions.BusinessLogic.Expressions
  4. {
  5.   public class CalculableExpression : IExpression
  6.   {
  7.     public CalculableExpression(IOperation operation)
  8.     {
  9.       Operation = operation;
  10.     }
  11.  
  12.     public double Result()
  13.     {
  14.       return Operation.Calculate().Result();
  15.     }
  16.  
  17.     protected IOperation Operation { get; set; }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.
 Выражение ведь может быть и очень простым, ведь верно? Например, просто "5". Создадим класс простого выражения:

  1. using CalculateExpressions.Domain;
  2.  
  3. namespace CalculateExpressions.BusinessLogic.Expressions
  4. {
  5.   public class SimpleExpression: IExpression
  6.   {
  7.     protected double Number { get; set; }
  8.  
  9.     public SimpleExpression(double number)
  10.     {
  11.       Number = number;
  12.     }
  13.  
  14.     public double Result()
  15.     {
  16.       return Number;
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.
  Опишем простые операции сложения и вычитания, опираясь ну сущности домена.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.Domain;
  3.  
  4. namespace CalculateExpressions.BusinessLogic.Operations
  5. {
  6.   public class Plus: BinaryOperation
  7.   {
  8.     public Plus(IExpression param1, IExpression param2):
  9.       base(param1, param2)
  10.     {
  11.       
  12.     }
  13.  
  14.     public override IExpression Calculate()
  15.     {
  16.       return new SimpleExpression(Parameter1.Result() + Parameter2.Result());
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.Domain;
  3.  
  4. namespace CalculateExpressions.BusinessLogic.Operations
  5. {
  6.   public class Minus: BinaryOperation
  7.   {
  8.     public Minus(IExpression param1, IExpression param2):
  9.       base(param1, param2)
  10.     {
  11.       
  12.     }
  13.  
  14.     #region IOperation Members
  15.  
  16.     public override IExpression Calculate()
  17.     {
  18.       return new SimpleExpression(Parameter1.Result() - Parameter2.Result());
  19.     }
  20.  
  21.     #endregion
  22.   }
  23. }
* This source code was highlighted with Source Code Highlighter.
  Раз уж в задании есть условие про расширяемость, то оставим остальные операции пока на потом. Заодно и проверим,действительно ли просто добавить еще пару операций.
  Итак, операции сложения и вычитания есть. Но ведь нужно еще как-то разобрать исходное строковое выражение - поделить его на наши сущности.
  Какая идея. Раз в условии сказано, что сама операция не должна зависеть от своего отображения, то распознавание операций нельзя делать в классах самих операций. Введем сущность распознавания операций:

  1. namespace CalculateExpressions.Domain
  2. {
  3.   public interface IOperationRecognition
  4.   {
  5.     IOperation Recognize(string expression, IRecognizer recognizer);
  6.   }
  7. }
* This source code was highlighted with Source Code Highlighter.
  Что такое IRecognizer. Назовем эту сущнсть менеджера распознавания. Пусть он будет выполнять поиск корректной операции. Сюда входит приоритет операций и возможность распознавания выражения в принципе. Вот его код:

  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace CalculateExpressions.Domain
  5. {
  6.   public interface IRecognizer
  7.   {
  8.     IOperation Recognize(String expression);
  9.     IEnumerable<IOperationRecognition> Recognitions { get; }
  10.   }
  11. }
* This source code was highlighted with Source Code Highlighter.
   IRecognizer подразумевает возможность внутри распознавания операции распознать и входящие в ее выражения. Какую операцию нужно вернуть, если выражение будет просто "5"? Верно, сделаем операцию, не изменяющую входящий параметр.

  1. using CalculateExpressions.Domain;
  2.  
  3. namespace CalculateExpressions.BusinessLogic.Operations
  4. {
  5.   public class EmptyOperation: UnaryOperation
  6.   {
  7.     public EmptyOperation(IExpression param)
  8.       : base(param)
  9.     {
  10.  
  11.     }
  12.  
  13.     public override IExpression Calculate()
  14.     {
  15.       return Parameter;
  16.     }
  17.   }
  18. }
* This source code was highlighted with Source Code Highlighter.
  Мы все еще не распознаем операции. Создадим для классов операций классы-распознаватели.

  1. using System;
  2. using CalculateExpressions.BusinessLogic.Expressions;
  3. using CalculateExpressions.BusinessLogic.Helpers;
  4. using CalculateExpressions.BusinessLogic.Operations;
  5. using CalculateExpressions.Domain;
  6.  
  7. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  8. {
  9.   public class PlusRecognition: IOperationRecognition
  10.   {
  11.     #region OperationRecognition Members
  12.  
  13.     public IOperation Recognize(String expression, IRecognizer recognizer)
  14.     {
  15.  
  16.       foreach (var parameters in SplitHelper.ParametersVariants(expression, '+'))
  17.       {
  18.         var arg1 = recognizer.Recognize(parameters.ParameterBefore);
  19.         if (arg1 == null)
  20.           continue;
  21.         var arg2 = recognizer.Recognize(parameters.ParameterAfter);
  22.         if (arg2 == null)
  23.           continue;
  24.         
  25.         return new Plus(new CalculableExpression(arg1), new CalculableExpression(arg2));
  26.       }
  27.       return null;
  28.     }
  29.  
  30.     #endregion
  31.   }
  32. }
* This source code was highlighted with Source Code Highlighter.

  1. using System;
  2. using CalculateExpressions.BusinessLogic.Expressions;
  3. using CalculateExpressions.BusinessLogic.Helpers;
  4. using CalculateExpressions.BusinessLogic.Operations;
  5. using CalculateExpressions.Domain;
  6.  
  7. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  8. {
  9.   public class MinusRecognition: IOperationRecognition
  10.   {
  11.     #region OperationRecognition Members
  12.  
  13.     public IOperation Recognize(String expression, IRecognizer recognizer)
  14.     {
  15.       foreach (var parameters in SplitHelper.ParametersVariants(expression, '-'))
  16.       {
  17.         var arg1 = recognizer.Recognize(parameters.ParameterBefore);
  18.         if (arg1 == null)
  19.           continue;
  20.         var arg2 = recognizer.Recognize(parameters.ParameterAfter);
  21.         if (arg2 == null)
  22.           continue;
  23.         return new Minus(new CalculableExpression(arg1), new CalculableExpression(arg2));
  24.       }
  25.       return null;
  26.     }
  27.  
  28.     #endregion
  29.   }
  30. }
* This source code was highlighted with Source Code Highlighter.
  Неизвестный класс SplitHelper выдает список возможных мест распознавания операций. Ведь, например сложений, в выражении может быть несколько, и мы не знаем, какое по счету нужно считать действительно правильным. Если операнды не удалось идентифицировать, то будем считать, что мы выбрали не ту позицию операции в выражении. Вот его код:

  1. using System;
  2.  
  3. namespace CalculateExpressions.BusinessLogic.Helpers
  4. {
  5.   public class SplitOpeartionParameters
  6.   {
  7.     public String ParameterAfter { get; protected set; }
  8.     public String ParameterBefore { get; protected set; }
  9.  
  10.     public SplitOpeartionParameters(String parameterBefore, String parameterAfter)
  11.     {
  12.       ParameterAfter = parameterAfter;
  13.       ParameterBefore = parameterBefore;
  14.     }
  15.   }
  16. }
* This source code was highlighted with Source Code Highlighter.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace CalculateExpressions.BusinessLogic.Helpers
  6. {
  7.   public class SplitHelper
  8.   {
  9.     public static IEnumerable<SplitOpeartionParameters> ParametersVariants(string expression, char splitter)
  10.     {
  11.       var list = new List<SplitOpeartionParameters>();
  12.       var str = expression.Split(splitter);
  13.       if (!expression.Contains(splitter))
  14.         return list;
  15.       for (var i = 0; i < str.Length - 1; i++)
  16.       {
  17.         var param1 = String.Empty;
  18.         var param2 = String.Empty;
  19.  
  20.         for (var j = 0; j <= i; j++)
  21.           param1 += str[j] + splitter;
  22.         param1 = param1.Substring(0, param1.Length - 1);
  23.         for (var j = i + 1; j < str.Length; j++)
  24.           param2 += str[j] + splitter;
  25.         param2 = param2.Substring(0, param2.Length - 1);
  26.  
  27.         list.Add(new SplitOpeartionParameters(param1, param2));
  28.       }
  29.       return list;
  30.     }
  31.   }
  32. }
* This source code was highlighted with Source Code Highlighter.
  Пустую операцию тоже нужно уметь распознавать:

  1. using System;
  2. using System.Globalization;
  3. using CalculateExpressions.BusinessLogic.Expressions;
  4. using CalculateExpressions.BusinessLogic.Operations;
  5. using CalculateExpressions.Domain;
  6.  
  7. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  8. {
  9.   public class EmptyRecognition: IOperationRecognition
  10.   {
  11.     #region OperationRecognition Members
  12.  
  13.     public IOperation Recognize(String expression, IRecognizer recognizer)
  14.     {
  15.       double res;
  16.       if (Double.TryParse(expression, NumberStyles.Float, CultureInfo.InvariantCulture, out res))
  17.         return new EmptyOperation(new SimpleExpression(res));
  18.       return null;
  19.     }
  20.  
  21.     #endregion
  22.   }
  23. }
* This source code was highlighted with Source Code Highlighter.
  Осталось только настроить менеджер распознавания:

  1. using System.Collections.Generic;
  2. using CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions;
  3. using CalculateExpressions.Domain;
  4.  
  5. namespace CalculateExpressions.BusinessLogic.Recognitions
  6. {
  7.   public class Recognizer : IRecognizer
  8.   {
  9.     public Recognizer()
  10.     {
  11.       Recognitions = new List<IOperationRecognition>
  12.                 {
  13.                       new PlusRecognition(),
  14.                       new MinusRecognition(),
  15.                       new EmptyRecognition()
  16.                 };
  17.     }
  18.  
  19.     #region IRecognizer Members
  20.  
  21.     public IOperation Recognize(string expression)
  22.     {
  23.       foreach (var recognition in Recognitions)
  24.       {
  25.         var res = recognition.Recognize(expression, this);
  26.         if (res != null)
  27.           return res;
  28.       }
  29.       return null;
  30.     }
  31.  
  32.     public IEnumerable<IOperationRecognition> Recognitions { get; protected set; }
  33.  
  34.     #endregion
  35.   }
  36. }
* This source code was highlighted with Source Code Highlighter.
  Порядок распознавания определяем, начиная с самого низкого приоритета - сложение, вычитание, пустая операция. Сложение ранее вычитания, потому что оно транзитивно.
  Как теперь вся эта штука взлетит.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.BusinessLogic.Recognitions;
  3.  
  4. namespace CalculateExpressions.Console
  5. {
  6.   class Program
  7.   {
  8.     static void Main(string[] args)
  9.     {
  10.       var recognizer = new Recognizer();
  11.       var exp = new CalculableExpression(recognizer.Recognize("5.3-1.5+12"));
  12.       System.Console.WriteLine(exp.Result());
  13.       System.Console.ReadKey();
  14.     }
  15.   }
  16. }
* This source code was highlighted with Source Code Highlighter.
  Результат выполнения - 15.8. Придумаем что-нибудь по-сложнее? Введем операции группировки, произведения и деления. Пусть их обозначения будут такими, как мы привыкли - "()", "*" и "/". Классы операций:

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.Domain;
  3.  
  4. namespace CalculateExpressions.BusinessLogic.Operations
  5. {
  6.   public class Brackets: UnaryOperation
  7.   {
  8.     public Brackets(IExpression param)
  9.       : base(param)
  10.     {
  11.       
  12.     }
  13.  
  14.     public override IExpression Calculate()
  15.     {
  16.       return new SimpleExpression(Parameter.Result());
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.Domain;
  3.  
  4. namespace CalculateExpressions.BusinessLogic.Operations
  5. {
  6.   public class Multiply: BinaryOperation
  7.   {
  8.     public Multiply(IExpression param1, IExpression param2)
  9.       : base(param1, param2)
  10.     {
  11.       
  12.     }
  13.  
  14.     public override IExpression Calculate()
  15.     {
  16.       return new SimpleExpression(Parameter1.Result() * Parameter2.Result());
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.Domain;
  3.  
  4. namespace CalculateExpressions.BusinessLogic.Operations
  5. {
  6.   public class Divide: BinaryOperation
  7.   {
  8.     public Divide(IExpression param1, IExpression param2)
  9.       : base(param1, param2)
  10.     {
  11.       
  12.     }
  13.  
  14.     public override IExpression Calculate()
  15.     {
  16.       return new SimpleExpression(Parameter1.Result() / Parameter2.Result());
  17.     }
  18.   }
  19. }
* This source code was highlighted with Source Code Highlighter.
   Ну и распознавания этих операций:

  1. using System;
  2. using System.Text.RegularExpressions;
  3. using CalculateExpressions.BusinessLogic.Expressions;
  4. using CalculateExpressions.BusinessLogic.Operations;
  5. using CalculateExpressions.Domain;
  6.  
  7. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  8. {
  9.   public class BracketsRecognition: IOperationRecognition
  10.   {
  11.     public Regex Condition { get; protected set; }
  12.  
  13.     public BracketsRecognition()
  14.     {
  15.       Condition = new Regex(@"^\((?<param>.*)\)$");
  16.     }
  17.  
  18.     #region OperationRecognition Members
  19.  
  20.     public IOperation Recognize(String expression, IRecognizer recognizer)
  21.     {
  22.       if (!Condition.IsMatch(expression))
  23.         return null;
  24.       var operation = recognizer.Recognize(Condition.Match(expression).Result("${param}"));
  25.       if (operation == null)
  26.         return null;
  27.       return new Brackets(new CalculableExpression(operation));
  28.     }
  29.  
  30.     #endregion
  31.   }
  32. }
* This source code was highlighted with Source Code Highlighter.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.BusinessLogic.Helpers;
  3. using CalculateExpressions.BusinessLogic.Operations;
  4. using CalculateExpressions.Domain;
  5.  
  6. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  7. {
  8.   public class MultiplyRecognition: IOperationRecognition
  9.   {
  10.     public IOperation Recognize(string expression, IRecognizer recognizer)
  11.     {
  12.       foreach (var parameters in SplitHelper.ParametersVariants(expression, '*'))
  13.       {
  14.         var arg1 = recognizer.Recognize(parameters.ParameterBefore);
  15.         if (arg1 == null)
  16.           continue;
  17.         var arg2 = recognizer.Recognize(parameters.ParameterAfter);
  18.         if (arg2 == null)
  19.           continue;
  20.         
  21.         return new Multiply(new CalculableExpression(arg1), new CalculableExpression(arg2));
  22.       }
  23.       return null;
  24.     }
  25.   }
  26. }
* This source code was highlighted with Source Code Highlighter.

  1. using CalculateExpressions.BusinessLogic.Expressions;
  2. using CalculateExpressions.BusinessLogic.Helpers;
  3. using CalculateExpressions.BusinessLogic.Operations;
  4. using CalculateExpressions.Domain;
  5.  
  6. namespace CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions
  7. {
  8.   public class DivideRecognition: IOperationRecognition
  9.   {
  10.     public IOperation Recognize(string expression, IRecognizer recognizer)
  11.     {
  12.       foreach (var parameters in SplitHelper.ParametersVariants(expression, '/'))
  13.       {
  14.         var arg1 = recognizer.Recognize(parameters.ParameterBefore);
  15.         if (arg1 == null)
  16.           continue;
  17.         var arg2 = recognizer.Recognize(parameters.ParameterAfter);
  18.         if (arg2 == null)
  19.           continue;
  20.         return new Divide(new CalculableExpression(arg1), new CalculableExpression(arg2));
  21.       }
  22.       return null;
  23.     }
  24.   }
  25. }
* This source code was highlighted with Source Code Highlighter.
  Теперь осталось обучить менеджера распознаваний новым операциям. Сделаем это следующим образом:

  1. using System.Collections.Generic;
  2. using CalculateExpressions.BusinessLogic.Recognitions.OperationRecognitions;
  3. using CalculateExpressions.Domain;
  4.  
  5. namespace CalculateExpressions.BusinessLogic.Recognitions
  6. {
  7.   public class Recognizer : IRecognizer
  8.   {
  9.     public Recognizer()
  10.     {
  11.       Recognitions = new List<IOperationRecognition>
  12.                 {
  13.                       new PlusRecognition(),
  14.                       new MinusRecognition(),
  15.                       new MultiplyRecognition(),
  16.                       new DivideRecognition(),
  17.                       new BracketsRecognition(),
  18.                       new EmptyRecognition()
  19.                 };
  20.     }
  21.  
  22.     #region IRecognizer Members
  23.  
  24.     public IOperation Recognize(string expression)
  25.     {
  26.       foreach (var recognition in Recognitions)
  27.       {
  28.         var res = recognition.Recognize(expression, this);
  29.         if (res != null)
  30.           return res;
  31.       }
  32.       return null;
  33.     }
  34.  
  35.     public IEnumerable<IOperationRecognition> Recognitions { get; protected set; }
  36.  
  37.     #endregion
  38.   }
  39. }
* This source code was highlighted with Source Code Highlighter.
  Пришлось добавить всего 3 строчки и весь функционал в игре! Опробуем выражение "5*(-1)/2.5+2*2+(+1-3.4)". Результат -0.4. Отлично, задачу можно считать решенной.

9 комментариев:

  1. Конструктор Recognizer - главная ошибка данной реализации. Необходимо список IOperationRecognition передавать из вне.

    ОтветитьУдалить
  2. Да, скорее всего ты прав. Нарушается принцип единственности ответственности. А какие есть неглавные ошибки?

    ОтветитьУдалить
  3. @hazzik - согласен класс Recognizer не должен явно зависить от классов реализаций операций, нужно использовать Dependency Injection

    ОтветитьУдалить
  4. Интересная статья интересный подход. Но будет ли это работать если выражении введенные пользователем не правильные например скобки не те или нет закрывающей скобки. А вы не пробовали смотреть в сторону формальных языков и грамматик?

    ОтветитьУдалить
  5. Если пользователь введет неверные, то программа работать не будет. Да, по большому счету нужно использовать формальную грамматику, синтаксический анализ через стек, например LL(1). Тогда можно будет и сообщение об ошибке передавать и т.д.

    ОтветитьУдалить
  6. Я не очень знаком с формальными грамматиками,
    но как я понял у вас не реализовано через формальные грамматика правильно?

    ОтветитьУдалить
  7. Да, у меня реализовано не через формальную грамматику. Зато получился хороший пример Domain-Driven Design, не правда ли?

    ОтветитьУдалить
  8. Не так. У вас вычисления оказались жестко прибиты к AST, а это значит что превратить этот интерпретатор в компилятор не получится без значительной правки кода. У вас получилась сильносвязная система где один компонент связан с другими. Причем даже интерфейсы тут не помогут, потому как такая связность заложена в распределение обязанностей межу классами.

    Если рассматривать с точки зрения SOLID, то у вас злостно нарушен SRP

    ОтветитьУдалить
  9. Если честно, не было цели делать компилятор.
    Дайте пример, где именно система получилась сильносвязанной? Где вы нашли злостное нарушение SRP?
    Если писать что-то сложнее, например компилятор, то, конечно, такой подход не работает, и, как я сказал выше, нужно будет использовать формальную грамматику и делать синтаксический анализатор.

    ОтветитьУдалить