Математические операции Pascal

[Gonzo]

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

Подкиньте хоть какую0нибудь идею.

Насколько я понимаю, сначала нужно написать процедуру со стринговым входным параметром (строка ввода), а выходным деревом.
После этого написать процедуру прямого обхода дерева для формирования префиксной формы записи выражения.
Еще вопрос: нет ни у кого модуля FParser?

За основу можно взять это:

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.

[capta1n]

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

вы все верно понимаете, только форма выражения будет не префиксная, а инфиксная - это обычная человеческая запись со скобками и операциями; получена такая форма записи симметричным обходом; или вам нужна префиксная - я что-то не очень понял, что вы хотите вывести из дерева - в задании сказано только сформировать

[Gonzo]

Сообщение от capta1n

я что-то не очень понял, что вы хотите вывести из дерева - в задании сказано только сформировать

Я еще сам до конца не понял, что нужно. Почитайте:
1. Прочитать со стандартного ввода арифметическое выражение. В нем могут содержаться операции +, -, *, /, exp, ln, sin, cos, числовые константы и переменная x. Выражение необходимо представить в виде дерева, листья которого – числа или переменные, а внутренние узлы – операции (при этом есть у операции только один аргумент, то один из сыновей может быть nil). Более подробная информация о вводимых данных находится ниже.
2. Найти производную выражения:
* 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)
Программа должна считать производную в линейном времени – нужно только раз (конкретное число раз) проходить по определенному фрагменту дерева (чтобы это было возможно, фрагменты, которые выступают несколько раз, должны быть «подцеплены» в нескольких местах)

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

4. Выписать ответ в формате таком же, как и формат входа (время пропорционально длине). Не стоит вставлять дополнительные пробелы или знаки конца строки (последняя строка должна заканчиваться знаком конца строки, так же как и предыдущие).
5. Освободить всю занятую память.

ВАЖНО: прочитанное выражение и результат необходимо держать в программе в виде (псевдо)дерева. Это часть задания, и нельзя это сделать иначе.
Спецификация входа/выхода
Выражение записано префиксно. Это значит, что запись выражения ни что иное как (индукционно):
* число, означающее постоянную, или
* символ 'x' означающий переменную x, или
* одна из надписей (без кавычек) '+', '-', '*', '/', 'exp', 'ln', 'sin', 'cos' означающая данную операцию, за которой следует запись первого аргумента, а дальше (только для первых четырех операция) запись второго аргумента.

Каждая из этих надписей (число, 'x', операция) записана в отдельной строке. Нету никаких пробелов, а также дополнительных знаков конца строки. Вход будет содержать максимум 1000 строк, а все числа будут помещаться в Integer (могут быть отрицательными). Можно считать, что на входе – правильное выражение: не надо проверять на ошибки входные данные и выводить сообщения о неправильных данных.
Производную выражения надо выписать на стандартный выход в таком же формате. Если программа не может посчитать производную какого-либо выражения, можно выписать на стандартный выход ошибок 'Производная не может быть посчитана' (без кавычек)
Если же программа может найти производную выражения, то кроме самой производной она должна выписать на стандартный выход ошибок в следующем порядке и по одному в строке: число узлов в памяти перед нахождением производной, после (но перед удалением из памяти ненужных уже узлов) и после удаления этих узлов.

[Gonzo]

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

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.

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

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

[Gonzo]

Уточнили задачу!
Оказывается:
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.Освобождается вся память.

[Gonzo]

Но удается строить дерево только при вводе выражения в инфиксной форме, а надо в префиксной. Причем число может состоять больше чем из одной цифры, а так же должны быть 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.