none
Парсер строки уравнения RRS feed

  • Вопрос

  • Добрый вечер господа. Подскажите пожалуйста советом, так как наверняка по тому вопросу, что у меня возник, есть если не готовые рецепты, то практические наработк :)

    Есть строка, представляющая собой арифметическое выражения типа C1+L12*5-R12/2=константа. В строке слева от знака равенства могут быть числа и переменные. Переменные R[индекс] - это сопротивление, оно вводится с клавиатуры и, фактически, это тоже константа :) Остальные значения нужно найти, решив уравнение. Даже не "остальные", а остальное, так как неизвестное будет одно. Знаки операций - "+-*\", без скобок. Хотел было сесть решать "влоб", то есть составляя алгоритмы с учетом приоритета операций, переноса через знак равенства констант и т.д., но решил создать тему здесь, в надежде что кто-то, может быть, сталкивался с таким и подскажет более оригинальное решение :)

    26 октября 2010 г. 18:41

Ответы

  • Предлагаю четыре варианта, работают используя c# с простыми операциями (-+*/).

    Формулу с переменными приведите к строковому выражению, и затем подставите выражение в парсер.

    1. вариант:

    var eng1 = Microsoft.JScript.Vsa.VsaEngine.CreateEngine();
    var result1 = Microsoft.JScript.Eval.JScriptEvaluate(
    @" var x =square(12,34,56);

      function square(C1,L12,R12) 

      { 
     return (30+C1)*L12-R12/30; 
      }; ", eng1);
                Console.WriteLine(result1);
                Console.ReadKey();
     2.вариант: 
    var result1 = new System.Data.DataTable().Compute("(30+12)*34-56/30"null);
                Console.WriteLine(result1);
                Console.ReadKey();

    3. вариант:

    var engine = new IronPython.Hosting.PythonEngine();
    double result = pythonEngine.EvaluateAs<double>("(30+12)*34-56/30");
     4.вариант: 
    public void calc()
    {
        Console.WriteLine("{0}", Evaluate("(30+12)*34-56/30"));
        Console.ReadKey();
    }

     

    public static double Evaluate(string expression)
            {
                return (double)new System.Xml.XPath.XPathDocument
                (
                 new System.IO.StringReader("<r/>")).CreateNavigator().Evaluate
                  (
                    string.Format("number({0})",
    new System.Text.RegularExpressions.Regex(@"/\*[^*]*\*+(?:[^/*][^*]*\*+)*/")
                        .Replace( expression, " ${1} ")
                        .Replace( "/"" div ")
                        .Replace( "%"" mod ")
                  )
                );
            }

    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:19
    31 октября 2010 г. 0:53
  • Пример реализации алгоритма для перевода обычного выражения в польскую (постфиксную) запись:

     

    using System.Collections;

    namespace Machine
    {
        class MachineCode
        {
            /// <summary>
            /// Перевод арифметических выражений в польскую запись.
            /// </summary>
            /// <param name="stExpression">Арифметическое выражение.</param>
            /// <returns>Арифметическое выражение в польской записи.</returns>
            public string ToMachineArithmetic(string stExpression)
            {
                stExpression += " ";

                int countBracket = 0;
                ArrayList arExpression = new ArrayList();

                int a = 0;
                for (int b = 0; b < stExpression.Length; b++)
                {
                    if (stExpression[b] == ' ')
                    {
                        if ((string)arExpression[arExpression.Add(stExpression.Substring(a, b - a))] == "(")
                        {
                            countBracket++;
                        }
                        a = b + 1;
                    }
                }

                int i = 0;
                int openBracket = 0, closeBracket = 0;
                while (true)
                {
                    if (countBracket == 0)
                    {
                        return SimpleTranslate(arExpression);
                    }
                    else if (i == arExpression.Count)
                    {
                        i = 0;
                    }
                    else
                    {
                        if ((string)arExpression[i] == "(")
                        {
                            openBracket = i;
                        }
                        else if ((string)arExpression[i] == ")")
                        {
                            closeBracket = i;

                            ArrayList arSimpleExpression = new ArrayList();

                            for (a = openBracket + 1; a < closeBracket; a++)
                            {
                                arSimpleExpression.Add(arExpression[a]);
                            }

                            arExpression[openBracket] = SimpleTranslate(arSimpleExpression);

                            // Удалим лишние элементы
                            arExpression.RemoveRange(openBracket + 1, closeBracket - openBracket);

                            countBracket--;

                            i = -1;
                        }
                    }
                    i++;
                }
            }

            private string SimpleTranslate(ArrayList arExpression)
            {
                int i = 0;
                int step = 1;

                while (true)
                {
                    if (arExpression.Count == 1)
                    {
                        return (string)arExpression[0];
                    }
                    else if (i == arExpression.Count)
                    {
                        i = 0;
                        step++;
                    }

                    switch(step)
                    {
                        case 1:
                            {
                                if ((string)arExpression[i] == "*" || (string)arExpression[i] == "/")
                                {
                                    arExpression[i - 1] = arExpression[i - 1] + " " + arExpression[i + 1] + " " + arExpression[i] + " ";

                                    // Удалим лишние элементы
                                    arExpression.RemoveRange(i,2);
                                }
                                else i++;
                            } break;
                        case 2:
                            {
                                if ((string)arExpression[i] == "+" || (string)arExpression[i] == "-")
                                {
                                    arExpression[i - 1] = arExpression[i - 1] + " " + arExpression[i + 1] + " " + arExpression[i] + " ";

                                    // Удалим лишние элементы
                                    arExpression.RemoveRange(i, 2);
                                }
                                else i++;
                            } break;
                    }
                }
            }
        }
    }

     

    static void Main(string[] args)
            {
                string mes2 = "( 5 + -3 ) * c - ( ( v / f ) - ( d + b ) )";
                string expr2 = new MachineCode().ToMachineArithmetic(mes2);
            }

    Выражение: ( 5 + -3 ) * c - ( ( v / f ) - ( d + b ) )

    Результат: 5 -3 +  c *  v f /  d b +  -  - 


    E-mail: Svatoslav.Pankratov@gmail.com
    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:18
    31 октября 2010 г. 12:45
  • Определить грамматику, разпарсить строку в дерево. Определить операции для трансформации дерева (выражения переменной через остальные ноды). Трансформировать. Вычислить. Как-то так.
    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:19
    28 октября 2010 г. 12:41

Все ответы

  • Совсем нет никаких идей?)
    28 октября 2010 г. 11:39
  • Определить грамматику, разпарсить строку в дерево. Определить операции для трансформации дерева (выражения переменной через остальные ноды). Трансформировать. Вычислить. Как-то так.
    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:19
    28 октября 2010 г. 12:41
  • Задача хорошо решается если представить все выражение в виде польской записи.

    Например, вот ваше выражение: ( C1 + L12 * 5 - R12 ) / 2 = const

     

    Представим выражение в виде польской записи:

    / - + * L12 5 C1 R12 2 = const

     

    Предположим, что надо найти L12. Вывод этой неизвестной будет выглядеть следующим образом:

    / - + * L12 5 C1 R12 2 = const

    - + * L12 5 C1 R12 = * const 2

    + * L12 5 C1 = + * const 2 R12

    * L12 5 = - + * const 2 R12 С1

    L12 = / - + * const 2 R12 С1 5

     

    Предположим, что надо найти R12. Вывод этой неизвестной будет выглядеть следующим образом:

    / - + * L12 5 C1 R12 2 = const

    - + * L12 5 C1 R12 = * const 2

    + * L12 5 C1 = + * const 2 R12

    - + * L12 5 C1 * const 2 = R12

    R12 = - + * L12 5 C1 * const 2

     

    Предположим, что надо найти C1. Вывод этой неизвестной будет выглядеть следующим образом:

    / - + * L12 5 C1 R12 2 = const

    - + * L12 5 C1 R12 = * const 2

    + * L12 5 C1 = + * const 2 R12

    C1 = - + * const 2 R12 * L12 5

     

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


    E-mail: Svatoslav.Pankratov@gmail.com
    • Предложено в качестве ответа Svyatoslav Pankratov 5 ноября 2010 г. 9:23
    30 октября 2010 г. 22:23
  • Предлагаю четыре варианта, работают используя c# с простыми операциями (-+*/).

    Формулу с переменными приведите к строковому выражению, и затем подставите выражение в парсер.

    1. вариант:

    var eng1 = Microsoft.JScript.Vsa.VsaEngine.CreateEngine();
    var result1 = Microsoft.JScript.Eval.JScriptEvaluate(
    @" var x =square(12,34,56);

      function square(C1,L12,R12) 

      { 
     return (30+C1)*L12-R12/30; 
      }; ", eng1);
                Console.WriteLine(result1);
                Console.ReadKey();
     2.вариант: 
    var result1 = new System.Data.DataTable().Compute("(30+12)*34-56/30"null);
                Console.WriteLine(result1);
                Console.ReadKey();

    3. вариант:

    var engine = new IronPython.Hosting.PythonEngine();
    double result = pythonEngine.EvaluateAs<double>("(30+12)*34-56/30");
     4.вариант: 
    public void calc()
    {
        Console.WriteLine("{0}", Evaluate("(30+12)*34-56/30"));
        Console.ReadKey();
    }

     

    public static double Evaluate(string expression)
            {
                return (double)new System.Xml.XPath.XPathDocument
                (
                 new System.IO.StringReader("<r/>")).CreateNavigator().Evaluate
                  (
                    string.Format("number({0})",
    new System.Text.RegularExpressions.Regex(@"/\*[^*]*\*+(?:[^/*][^*]*\*+)*/")
                        .Replace( expression, " ${1} ")
                        .Replace( "/"" div ")
                        .Replace( "%"" mod ")
                  )
                );
            }

    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:19
    31 октября 2010 г. 0:53
  • Спасибо всем. Господа, я тут написал небольшой пример разбора функции в дерево через рекурсию. Когда алгоритм выполняется, то судя по работе все должно быть правильно, но затем, при проверке отдельной функций, получается какая-то белиберда. Подскажите, где ошибка.

    Класс узла дерева

     

      public class usrTree
      {
        public int intA; //Первый операнд в узле
        public int intB; //Второй операнд в узле
        public char chOperSymb; //Знак операции в узле
        public usrTree treeNodeChildLeft; //Ссылка на левую ветвь
        public usrTree treeNodeChildRight; //Ссылка на правую ветвь
        public usrTree treeNodeParent; //Ссылка на родителя
    
        public usrTree(int _a, int _b, char _chOperSymb, usrTree _treeNodeParent)
        {
          intA = _a;
          intB = _b;
          chOperSymb = _chOperSymb;
          treeNodeParent = _treeNodeParent;
        }
    
        public usrTree()
        {
    
        }
    
      }
    
    //Функция заполнения дерева
        public void Zapol(string strBuf, usrTree BufTree, string strStatus)
        {
          int i=0;
          int j = 0;
          char chOper;
          string s1 = "";
          string s2 = "";
          //Если найдена операция + или -, то делим строку на 2 части:
          //Слева - операция до знака +/-, справа - остальное
          if ((strBuf.IndexOf('+') != -1) || (strBuf.IndexOf('-') != -1))
          {
            i = strBuf.IndexOfAny(strOperA.ToCharArray());
            //Создаем новый узел, предок которого передаваемый в фукнцию узел
            usrTree usrNewTree = new usrTree(0, 0, strBuf[i], BufTree);
            //Если узел не центральный
            if (strStatus != "Center")
            {
              if (strStatus == "Left") BufTree.treeNodeChildLeft = usrNewTree;
              if (strStatus == "Right") BufTree.treeNodeChildRight = usrNewTree;
              //Если узел-предок имел операцию +/-, то необходимо обнулить одно из слогаемых
              if ((BufTree.chOperSymb == '+') || (BufTree.chOperSymb == '-'))
              {
                if (strStatus == "Left") BufTree.intA = 0;
                if (strStatus == "Right") BufTree.intB = 0;
              }
            }
            else
            {
              //Если узел центральный, то сохраняем ссылку на вершину
              usrNewTree.treeNodeParent=null;
              MainTree = usrNewTree;
            }
            //Выделяем строку до знака +/-
            s1 = strBuf.Substring(0, i);
            MessageBox.Show(s1);
            //Выделяем строку после знака +/-
            s2 = strBuf.Substring(i + 1, strBuf.Length - i - 1);
            MessageBox.Show(s2);
            //Рекурсия с указанием ветви
            Zapol(s1, usrNewTree, "Left");
            Zapol(s2, usrNewTree, "Right");
          }
          //Если строка поделена на подстроки без знаков +/-
          else
          {
            //Если строка не содержит и других знаков, то есть она - число
            if ((strBuf.IndexOf('*') == -1) && (strBuf.IndexOf('/') == -1))
            {
              if (strStatus == "Left")
              {
                BufTree.intA = Convert.ToInt32(strBuf);
                BufTree.treeNodeChildLeft = null;
              }
              if (strStatus == "Right")
              {
                BufTree.intB = Convert.ToInt32(strBuf);
                BufTree.treeNodeChildRight = null;
              }
            }
            //Если строка содержит другие знаки (* или /)
            else
            {
              if ((BufTree.chOperSymb == '+') || (BufTree.chOperSymb == '-'))
              {
                if (strStatus == "Left") BufTree.intA = 0;
                if (strStatus == "Right") BufTree.intB = 0;
              }
              //Если в строке есть несколько знаков операции
              if (!(StrForCompare(strBuf)))
              {
                MessageBox.Show("1");
                //Находим символ первой операции
                i = ParseEasyStr(strBuf);
                j = strBuf.Length;
                chOper = strBuf[i];
                //Копируем число до символа
                s1 = strBuf.Substring(0, i);
                MessageBox.Show(s1);
                //Копируем строку после символа
                s2 = strBuf.Substring(i+1, j-1-i);
                MessageBox.Show(s2);
                //Создаем новый узел
                usrTree usrNewTree = new usrTree(Convert.ToInt32(s1), 1, chOper, BufTree);
                if (strStatus == "Left") BufTree.treeNodeChildLeft = usrNewTree;
                if (strStatus == "Right") BufTree.treeNodeChildRight = usrNewTree;
                usrNewTree.treeNodeChildLeft = null;
                Zapol(s2, usrNewTree, "Right");
              }
              //Если в строке - один знак операции, то есть слева и справа от знака - числа
              else
              {
                MessageBox.Show("2");
                i = ParseEasyStr(strBuf);
                j = strBuf.Length;
                chOper=strBuf[i];
                //Выделяем первое число
                s1 = strBuf.Substring(0, i);
                MessageBox.Show(s1);
                //Выделяем второе число
                s2 = strBuf.Substring(i + 1, j - i - 1);
                MessageBox.Show(s2);
                //Создаем новый узел
                usrTree usrNewTree = new usrTree(Convert.ToInt32(s1), Convert.ToInt32(s2),chOper, BufTree);
                if (strStatus == "Left") BufTree.treeNodeChildLeft = usrNewTree;
                if (strStatus == "Right") BufTree.treeNodeChildRight = usrNewTree;
                usrNewTree.treeNodeChildLeft = null;
                usrNewTree.treeNodeChildRight = null;
                EndTree = usrNewTree;
              }
            }
    
          }
        }

     

     

    Затем я захотел проверить работу, пробежав по одной из веток функций

     

        public void ShowTreeFromEnd(usrTree bufTree)
        {
          MessageBox.Show(bufTree.intA.ToString() + bufTree.chOperSymb.ToString() + bufTree.intB.ToString());
          while (bufTree.treeNodeParent != null)
          {
            bufTree = bufTree.treeNodeParent;
            ShowTree(bufTree);
          }
        }

    И что-то мимо совсем, где то зацикливание получается, связи неправильно расставлены

    31 октября 2010 г. 8:32
  • Если что-то непонятно, могу прислать проект. После нахождения ошибки уже будет очень просто решить это уравнение )
    31 октября 2010 г. 10:16
  • Пример реализации алгоритма для перевода обычного выражения в польскую (постфиксную) запись:

     

    using System.Collections;

    namespace Machine
    {
        class MachineCode
        {
            /// <summary>
            /// Перевод арифметических выражений в польскую запись.
            /// </summary>
            /// <param name="stExpression">Арифметическое выражение.</param>
            /// <returns>Арифметическое выражение в польской записи.</returns>
            public string ToMachineArithmetic(string stExpression)
            {
                stExpression += " ";

                int countBracket = 0;
                ArrayList arExpression = new ArrayList();

                int a = 0;
                for (int b = 0; b < stExpression.Length; b++)
                {
                    if (stExpression[b] == ' ')
                    {
                        if ((string)arExpression[arExpression.Add(stExpression.Substring(a, b - a))] == "(")
                        {
                            countBracket++;
                        }
                        a = b + 1;
                    }
                }

                int i = 0;
                int openBracket = 0, closeBracket = 0;
                while (true)
                {
                    if (countBracket == 0)
                    {
                        return SimpleTranslate(arExpression);
                    }
                    else if (i == arExpression.Count)
                    {
                        i = 0;
                    }
                    else
                    {
                        if ((string)arExpression[i] == "(")
                        {
                            openBracket = i;
                        }
                        else if ((string)arExpression[i] == ")")
                        {
                            closeBracket = i;

                            ArrayList arSimpleExpression = new ArrayList();

                            for (a = openBracket + 1; a < closeBracket; a++)
                            {
                                arSimpleExpression.Add(arExpression[a]);
                            }

                            arExpression[openBracket] = SimpleTranslate(arSimpleExpression);

                            // Удалим лишние элементы
                            arExpression.RemoveRange(openBracket + 1, closeBracket - openBracket);

                            countBracket--;

                            i = -1;
                        }
                    }
                    i++;
                }
            }

            private string SimpleTranslate(ArrayList arExpression)
            {
                int i = 0;
                int step = 1;

                while (true)
                {
                    if (arExpression.Count == 1)
                    {
                        return (string)arExpression[0];
                    }
                    else if (i == arExpression.Count)
                    {
                        i = 0;
                        step++;
                    }

                    switch(step)
                    {
                        case 1:
                            {
                                if ((string)arExpression[i] == "*" || (string)arExpression[i] == "/")
                                {
                                    arExpression[i - 1] = arExpression[i - 1] + " " + arExpression[i + 1] + " " + arExpression[i] + " ";

                                    // Удалим лишние элементы
                                    arExpression.RemoveRange(i,2);
                                }
                                else i++;
                            } break;
                        case 2:
                            {
                                if ((string)arExpression[i] == "+" || (string)arExpression[i] == "-")
                                {
                                    arExpression[i - 1] = arExpression[i - 1] + " " + arExpression[i + 1] + " " + arExpression[i] + " ";

                                    // Удалим лишние элементы
                                    arExpression.RemoveRange(i, 2);
                                }
                                else i++;
                            } break;
                    }
                }
            }
        }
    }

     

    static void Main(string[] args)
            {
                string mes2 = "( 5 + -3 ) * c - ( ( v / f ) - ( d + b ) )";
                string expr2 = new MachineCode().ToMachineArithmetic(mes2);
            }

    Выражение: ( 5 + -3 ) * c - ( ( v / f ) - ( d + b ) )

    Результат: 5 -3 +  c *  v f /  d b +  -  - 


    E-mail: Svatoslav.Pankratov@gmail.com
    • Помечено в качестве ответа Abolmasov Dmitry 23 ноября 2010 г. 15:18
    31 октября 2010 г. 12:45
  • Спасибо. Жду помощи по дереву )))
    31 октября 2010 г. 13:30
  • Если ответ был Вам полезен, ставьте пожалуйста на против полезного ответа плюсик =)
    E-mail: Svatoslav.Pankratov@gmail.com
    31 октября 2010 г. 23:45