Парсер математических операций

[dr.Jekill]

Прочитать со стандартного ввода арифметическое выражение.
(Пускай это будет строка)
В нем могут содержаться операции +, -, *, /, exp, ln, sin, cos, числовые константы и переменная x.
Выражение необходимо представить в виде дерева, листья которого – числа или переменные, а внутренние узлы – операции (при этом есть у операции только один аргумент, то один из сыновей может быть nil (пускай это будет правый)). Результатом должна быть структура указателей, описанная так ,как предыдущая, но не обязательно дерево. Если с правой стороны равенства находятся подвыражения исходного выражения, то не стоит создавать в памяти новых узлов, а использовать уже существующие. В частности, это относится ко всему выражению exp(A). Прочитанное выражение и результат необходимо держать в программе в виде (псевдо)дерева.

Да, конечно, что-то много понаписал. Для начала нужно просто написать процедуру (или функцию) со стринговым входным параметром, содержащим строку ввода и чтоб выходным было дерево.
Например, для выражения: (a-(c+d))*(e/(f-g))
*
/ \
/ \
- :
/ \ / \
a + e -
/ \ / \
c d f g
Потом, насколько я понимаю, нужна процедура прямого обхода дерева для получения префиксной формы выражения.

[dr.Jekill]

За основу для процедуры можно взять это:

Код: Выделить всё

uses crt;
Type Vhod=char;{integer}
     U=^Tree;
     Tree=Record
     Inf:VHOD;
     L,R:U;
End;
var ResTree:U;
    s:string;
    i:byte;
{процедура добавления числа в двоичное дерево}
Procedure InsRec(x:char{integer};Var Tree:U);
Begin
 If Tree = Nil Then
  Begin
   New(Tree);
   Tree^.L := Nil;
   Tree^.R := Nil;
   Tree^.Inf := x
  End
  Else
  If x < Tree^.inf Then
  InsRec(x,Tree^.L)
  Else InsRec(x,Tree^.R);
End;


begin
clrscr;
writeln('Vvedite vyrazhenie: ');
readln(s);
for i:=1 to length(s) do
 begin
  insrec(s[i],ResTree);
 end;
end.

[dr.Jekill]

С этим уже можно работать...

Код: Выделить всё

uses Crt;
type TreePointer = ^tree;
 tree = record
 data: char;
 left: TreePointer;
 right: TreePointer;
end;
var
root, dummy: TreePointer;
ch:char;

function STree(root, r:TreePointer; data: char):TreePointer;
 begin
  if r = nil then
   begin
    new(r);
    r^.left := nil;
    r^.right := nil;
    r^.data := data;
    if data < root^.data then root^.left := r
    else root^.right := r;
    STree := r;
   end
   else
    begin
     if data<r^.data then STree := STree(r, r^.left, data)
     else STree := STree(r, r^.right, data)
    end;
 end;

procedure PrintTree(r: TreePointer; n: integer);
var i:integer;
 begin
  if r<>nil then begin
  PrintTree(r^.left, n+1);
  for i := 1 to n do write('   ');
  Writeln(r^.data);
  PrintTree(r^.right, n+1);
 end;
end;

begin
 clrscr;
 root := nil;
 repeat
 Write('Vvodite dannye (dlia zavershenia vvoda nazhmite probel) -> ');
 ch := ReadKey;
 Writeln(ch);
 if root= nil then root := STree(root, root, ch)
 else dummy := STree(root, root, ch);
 ch := UpCase(ch);
 until ch =' ';
 PrintTree(root, 0);
 readln;
end.

Единственное тут симметричный проход.

[dr.Jekill]

Уточню задание:
Пусть дана строка, содержащая выражение в инфиксной форме, где могут содержаться: +, -, *, /, exp, ln, sin, cos.
1. Написать процедуру построения по этой строке дерева выражений.
2. Написать процедуру прямого обхода дерева выражений с составлением списка меток (значений узлов) дерева выражений.

[Naeel Maqsudov]

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

[dr.Jekill]

А реальное построение дерева - это обязательное условие?

К сожалению это одно из условий задачи: "прочитанное выражение необходимо держать в программе в виде дерева." А так у меня тоже после 40 минут "гугления" накопилось множество исходников, использующих алгоритм Дейкстры, рекурсивные функции и т.д. Вообщем что-угодно, но нужного - крупицы.
Так что, буду признателен за любую помощь.

[dr.Jekill]

Если в строчке нет символов операций, то это "лист", оконечная вершина.
Иначе ищем символ операции с минимальным приоритетом (которая будет выполняться последней) и добавляем в дерево вершину для этой операции. Левое и правое поддеревья для этой вершины находим рекурсивно, для подстроки, остающейся слева и справа от найденного символа операции.
Но при реализации проблема за проблемой. - Не хватает опыта в работе с деревьями. Что называется кто чем может...

[dr.Jekill]

Уточнили задачу!
Оказывается:
1.Вводится выражение в префиксной форме: одна строка - одна константа (все константы целочисленные), одна переменная, одна операция (+, -, *, /, exp, ln, sin, cos).
2.Строится дерево этого выражения.
3.Производится обход дерева и формируется линейный список, содержащий промежуточные результаты нахождения производной.
* D(число) = число_0
* D(переменная_x) = переменная_1
* D(A + B) = D(A) + D(B)
* D(A - B) = D(A) - D(B)
* D(A * B) = D(A) * B + A * D(B)
* D(A / B) = (D(A) * B - A * D(B)) / (B * B)
* D(exp A) = (exp A) * D(A)
* D(ln A) = (число_1 / A) * D(A)
* D(sin A) = (cos A) * D(A)
* D(cos A) = (число_0 - sin A) * D(A)
Последний элемент - производная всего выражения. Если производная не найдена выводится сообщение.
(Если с правой стороны равенства находятся подвыражения исходного выражения, то не стоит создавать в памяти новых узлов, а использовать уже существующие. В частности, это относится ко всему выражению exp(A).Важно: нужно только раз (конкретное число раз) проходить по определенному фрагменту дерева (чтобы это было возможно, фрагменты, которые выступают несколько раз, должны быть «подцеплены» в нескольких местах)).
4.Освобождаются неиспользуемые узлы дерева выражения.
5.Выводятся узлы дерева выражения, и их производная в зависимости от операции.
Например:
>2 0
>4 0
>2+4 0
и т.д.
Так же должно быть выведенно число узлов в памяти перед нахождением производной, после (но перед удалением из памяти ненужных уже узлов) и после удаления этих узлов.
6.Освобождается вся память.

[dr.Jekill]

Но удается строить дерево только при вводе выражения в инфиксной форме, а надо в префиксной. Причем число может состоять больше чем из одной цифры, а так же должны быть exp, ln, sin, cos. По идее считывать надо из файла *.in, где каждая строка одна константа, один оператор (+, -, *, /, exp, ln, sin, cos) или переменная x, но думаю просто написать процедуру которая формировала бы строку из этого файла.
Возможно ли всё организовать таким образом?

Код: Выделить всё

uses Crt;
type TreePointer = ^tree;
 tree = record
 data: string;
 left: TreePointer;
 right: TreePointer;
end;

const
  MAXPRIORITY=3;
  SIGNS=['+','-','*','/'];

var
root, dummy: TreePointer;
ch:char;
stroka:string;

function PriorSimv (sign: char): integer;
begin
  case sign of
    '+','-': PriorSimv:=0;
    '*','/': PriorSimv:=1;
  end;
end;

function PriorStr (f:string): integer;
begin
 if (f='ln') or (f='exp') or (f='cos') or (f='sin')
 then PriorStr:=0;
end;

function BuildTree (str: string): TreePointer;
var
  tmp: TreePointer;
  i: integer;
  priormin, imin: integer;
  leftstr, rightstr: string;
  flag:boolean;
begin
 if length(str)=1 then
  begin
   New(tmp);
   tmp^.data:=str[1];
   tmp^.left:=nil;
   tmp^.right:=nil;
   BuildTree:=tmp;
  end
  else
   begin
    i:=length(str);flag:=false;
    priormin:=MAXPRIORITY;
    imin:=i;
    while i>=1 do
     begin
      if ((str[i] in SIGNS) and (PriorSimv(str[i])<priormin)) then
       begin
        priormin:=PriorSimv(str[i]);
        imin:=i;
       end;
      i:=i-1;
     end;
    New(tmp);
    tmp^.data:=str[imin];
    leftstr:=Copy(str,1,imin-1);
    rightstr:=Copy(str,imin+1,length(str)-imin);
    tmp^.left:=BuildTree(leftstr);
    tmp^.right:=BuildTree(rightstr);
    BuildTree:=tmp;
  end;
end;

procedure Infiks(r:TreePointer);
 begin
  if r<>nil then begin
  Infiks(r^.left);
  Write(r^.data);
  Infiks(r^.right);
 end;
end;

procedure Prefiks(r:TreePointer);
 begin
  if r<>nil then
   begin
    Write(r^.data);
    Prefiks(r^.left);
    Prefiks(r^.right);
   end;
 end;

procedure Postfiks(r:TreePointer);
 begin
  if r<>nil then
   begin
    Postfiks(r^.left);
    Postfiks(r^.right);
    Write(r^.data);
   end;
 end;

begin
 clrscr;
 root := nil;
 writeln('Vvedite stroku: ');
 readln(stroka);
 root := BuildTree(stroka);
 writeln('Priamoi obhod: ');
 Prefiks(root);
 writeln;
 writeln('Obratnyi obhod: ');
 Postfiks(root);
 writeln;
 writeln('Simmetrichnyi obhod: ');
 Infiks(root);
 readln;
end.

[dr.Jekill]

С деревьями разобрался. Тему можно закрывать.