Информатика ← ЛабораторныеЛабораторная работа №24

Преобразование арифметических выражений

Задание

Составить программу выполнения заданных преобразований арифметических выражений с применением деревьев. Преобразоване выражения в дерево рекомендуется осуществлять одним из известных методов (Рутисхаузера, Дейкстры и др.). Операнды в обрабатываемых выражениях могут быть целого или вещественного типа (по усмотрению преподавателя). Задания могут быть переформулированы и для булевского типа. Преобразование выражения реализовать в виде набора подпрограмм. Программа должна вводить и печатать выражения в исходном (тесктовом) виде, преобразовывать их в деревья, выполнять заданные преобзования путем обращения к подрпрограммам и печатать результаты в виде дерева и в текстовом представлении.

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

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

Варианты преобразований

  1. Упростить выражения, выполнив сложение:

    2 + 3 --> 5,
    (-2 + b + 4) * k --> (2 + b) * k.
    
  2. Упростить выражения, выполнив вычитание:

         3 - 5 --> -2,
         5 + b - 3 --> 2 + b.
    
  3. Упростить выражения, выполнив умножение:

         2 * b * 2 --> 4 * b.
    
  4. Упростить выражения, выполнив деление:

         4 * a / 2 --> 2 * b.
    
  5. Упростить выражения, выполнив возведение числа в степень с целым показателем:

        2^3 --> 8.
    
  6. Упростить выражения, выполнив приведение подобных членов.

  7. Редуцировать выражения, заменив операцию умножения переменно на целое число n на сумму n слагаемых:

        a * 3 --> a + a + a.
    
  8. Редуцировать выражения, заменив оперцию возведения переменной в целую степень n на произведение n слагаемых:

        a ^ 3 --> a * a * a.
    
  9. Умножение переменной на сумму заменить на сумму произведений.

  10. Умножение переменной на разность заменить на разность произведений.
  11. Вынести общие сомножители (переменные и константы) из суммы.
  12. Вынести общие сомножители (переменные и константы) из разности.
  13. Упростить выражения, убрав из него все произведения, в которых в качестве сомножителя используется нуль.
  14. Убрать из выражений все слагаемые, равные нулю.
  15. Убрать из выражений все сомножители, равные единице.
  16. Убрать из частных все делители, равные единице.
  17. Перемножить степени с одинаковыми основаниями (в простейшем случае можно рассматривать основания, состоящие из одной переменной или константы):

        2^a * a^k --> a^(2 + k).
    
  18. Вынести из произведений унарные минусы:

        a * (-b) * 3 --> -(a * b * 3),
        a * (-b) * 4 * (-5) --> a * b * 4 * 5. 
    
  19. Упростить сложные (многоэтажные) дроби:

        (a / b) / c --> a / (b * c),
        a / (b / c) --> (a / b) * c.
    
  20. Подсчитать количество операндов (переменных и констант) в выражении.

  21. Подсчитать количество переменных, используемых в данном выражении.
  22. Подсчитать количество целых констант, используемых в выражении.