unit Unit1;
interface
uses  Windows, Messages, SysUtils, Variants, Classes,
 Graphics, Controls, Forms, Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button__Do: TButton;
    Memo1: TMemo;
    procedure Button__DoClick(Sender: TObject);

  public
   procedure Clear;
   procedure Print(s1: string; Show_Number: Boolean = false);
   procedure PrintEmpty;

  end;


type
zapis = record
 nam: string;
end;

ukaz = record
 level, index: Integer;
end;

uzel = record
 zap: zapis;
 tek: ukaz;
 up: ukaz;
 down: Array of ukaz;
 resultat: Integer;
end;


var
 Form1: TForm1;
 Number_Print: Integer;

 tree: Array of Array of uzel;

implementation
{$R *.dfm}



function IsDigitChar(c1: Char): Boolean;
begin
 Result := false;
 if ( (c1 >= '0') and (c1 <= '9') )
 then Result := true;
end;

function IsDigitStr(s: string; UsePoint: Boolean = false): Boolean;
var
 i, Leng: Integer;
 Point1, Point2: string;
begin
 Point1 := '.';
 Point2 := ',';
 Result := true;
 Leng := Length(s);
 for i:=1 to Leng do
  if (not IsDigitChar(s[i])) then
   begin
    if (i = 1) and (s[1] = '-') then
     begin

      if (Leng = 1) then
       begin
        Result := false;
        break;
       end;

     end
    else
    if UsePoint and ((s[i] = Point1) or (s[i] = Point2)) then
     begin
     end
    else
     begin
      Result := false;
      break;
     end;
   end;
end;


procedure TForm1.Clear; begin Number_Print := 0; Memo1.Clear; end;
procedure TForm1.Print(s1: string; Show_Number: Boolean = false);
begin
 Inc(Number_Print);
 if (Show_Number) then
   s1 := IntToStr(Number_Print) + ') ' + s1;
 Memo1.Lines.Add(s1);
end;
procedure TForm1.PrintEmpty; begin Print(''); end;


procedure clr_uzel;
begin
 SetLength(tree, 0);
end;

function add_uzel(level: Integer;  nam: string;  up: ukaz): ukaz;
var
 Leng, resultat
 : Integer;
begin
 Leng := Length(tree);
 if (level > (Leng - 1)) then
  begin
   SetLength( tree,  level + 1 );
   SetLength( tree[level],   0 );
  end;

 Leng := Length( tree[level] );
 SetLength( tree[level], Leng + 1 );
 tree[level][Leng].zap.nam := nam;
 tree[level][Leng].tek.level := level;
 tree[level][Leng].tek.index := Leng;
 tree[level][Leng].up := up;
 SetLength( tree[level][Leng].down, 0 );

 if IsDigitStr(nam)
 then resultat := StrToInt(nam)
 else resultat := 0;
 tree[level][Leng].resultat := resultat;

 Result := tree[level][Leng].tek;
end;


function do_oper( operation: string;  resultat_1, resultat_2: Integer ): Integer;
begin
 Result := 0; 
 if (operation = '+') then Result := resultat_1 + resultat_2;
 if (operation = '-') then Result := resultat_1 - resultat_2;
 if (operation = '*') then Result := resultat_1 * resultat_2;
end;


procedure TForm1.Button__DoClick(Sender: TObject);
var
 i, k, z,
 Leng, Leng2, Leng3,
 index, resultat
 : Integer;

 up_1, up_2, up_3,
 up_4, up_5
 : ukaz;

 s1, operation
 : string;
begin
 // [url=https://plana.mybb.ru/viewtopic.php?id=144]О склеивании выхода парсера со входом сканера[/url]
 // https://russianblogs.com/article/62501151692/
 // 1 + 3 * (4-1) + 2 = 12
 clr_uzel;
 up_1.level := 0;
 up_1.index := 0;

 up_2 := add_uzel(0, '+', up_1);

 up_3 := add_uzel(1, '+', up_2);
         add_uzel(1, '2', up_2);

         add_uzel(2, '1', up_3);
 up_4 := add_uzel(2, '*', up_3);

         add_uzel(3, '3', up_4);
 up_5 := add_uzel(3, '-', up_4);

         add_uzel(4, '4', up_5);
         add_uzel(4, '1', up_5);


 // show uzel by level, for correctness
 Leng := Length(tree);
 for i:=0 to (Leng - 1) do
  begin

   s1 := '';
   Leng2 := Length( tree[i] );
   for k:=0 to (Leng2 - 1) do
    begin
     s1 := s1 + tree[i][k].zap.nam + '  ';
    end;

   Print(s1);
  end;


 // building of array "down"
 Leng := Length(tree);
 for i:=(Leng - 1) downto 1 do
  begin

   Leng2 := Length( tree[i] );
   for k:=0 to (Leng2 - 1) do
    begin
     index := tree[i][k].up.index;
     Leng3 := Length( tree[i - 1][index].down );
     SetLength( tree[i - 1][index].down, Leng3 + 1 );
     tree[i - 1][index].down[Leng3].level := i;
     tree[i - 1][index].down[Leng3].index := k;
    end;

  end;


 // calculation of result
 Leng := Length(tree);
 for i:=(Leng - 2) downto 0 do
  begin

   Leng2 := Length( tree[i] );
   for k:=0 to (Leng2 - 1) do
    begin

     operation := tree[i][k].zap.nam;

     Leng3 := Length( tree[i][k].down );
     if (Leng3 > 0) then
      begin

       resultat := 0;

       for z:=0 to (Leng3 - 1) do
        begin
         index := tree[i][k].down[z].index;

         if (z = 0)
         then resultat := tree[i + 1][index].resultat
         else resultat := do_oper( operation,  resultat,  tree[i + 1][index].resultat );
        end;

       tree[i][k].resultat := resultat;

      end;

    end;

  end;


 resultat := tree[0][0].resultat;
 s1 := 'resultat = ' + IntToStr(resultat);
 Print(s1);
end;

end.

#ifndef ASTTREE_H
#define ASTTREE_H

/*******************************************************

//=======================================================
// "Стандартный" узел с одним/двумя дочерними
//=======================================================
typedef struct {
  int type;
  unsigned long int kinds_N;	// число "дочек"
  unsigned long int left;    // индекс левого дочернего узла
  unsigned long int right;    // индекс правого дочернего узла
  void * none;        	// не используется
} ASTnode_base;

//=======================================================
// "Расширенный" узел с тремя и более дочерними
//=======================================================
typedef struct {
  int type;
  unsigned long int kinds_N;	// число "дочек"
  unsigned long int length;    //размер массива
  unsigned long int count;    //текущий индекс на всякий случай
  void * kinds;        	//указатель на массив индексов дочерних узлов
} ASTnode_wide;        	

//=======================================================
// Узел - лист
//=======================================================
typedef struct {
  int type;
  unsigned long int kinds_N;
  unsigned long int length;    //размер массива
  unsigned long int count;    //текущий индекс на всякий случай
  void * lexema;
} ASTnode_leaf;
********************************************************/

//=======================================================
// Обобщенный узел дерева
//=======================================================
typedef struct {
  int type;
  unsigned long int kinds_N;
  unsigned long int parent;    	// индекс родителя
  double value;
  union {
  	unsigned long int left;    	// индекс левого дочернего узла
  	unsigned long int length;    // или размер массива
  };
  union {
  	unsigned long int right;    // индекс правого дочернего узла
  	unsigned long int count;    //или текущий индекс "дочки" на всякий случай
  };
  union {
  	void * kinds;        	//указатель на массив индексов дочерних узлов
  	void * lexema;        	//или указатель на лексему
  };
  
} TASTnode;
//=========================================================
// AST - дерево
//=========================================================
typedef struct {
  unsigned long int count;    	// текущий узел
  unsigned long int nodes_N;    // количество узлов в дереве
  unsigned long int length;    	// размер массива
  TASTnode *nodes;        	// Указатель на массив узлов
} TASTtree;

//==========================================================
// Начальная инициализация AST - дерева
//==========================================================
int ASTinit(TASTtree *tree)
{
	if (tree->nodes == NULL)
    tree-> nodes = (TASTnode*) malloc(1000); //выделяем память на 1000 узлов
	else
    return -1;	//память уже выделена ранее	
	tree -> length = 1000;
	tree -> nodes_N = 0;
	tree -> count = 0;
	tree -> nodes[0].type = 0;
	tree -> nodes[0].kinds_N = 0;
	return 0; 	// без ошибок
}
//==========================================================
// Освобождение памяти AST - дерева
//==========================================================
int ASTfree(TASTtree *tree)
{
	//********************************************
	// Сначала нужно пробежаться по узлам и при 
	// необходимости освободить память kinds
	//********************************************
	if (tree -> nodes != NULL){
    free(tree -> nodes); //освобождаем память
    tree -> nodes  = NULL;
    tree -> length = 0;
    tree -> nodes_N = 0;
    return 0; 	// без ошибок
    }
	else
    return -1;	//память не была выделена ранее	
	
}
//==========================================================
// Добавление дочернего узла AST - дерева и переход к нему
//==========================================================
int ASTadd(TASTtree *tree, int type, double value)
{
	//если массив узлов полностью заполнен
	if (tree -> length == tree -> nodes_N)
	{
	  ; // выделяем дополнительную память
	}
	if (tree -> nodes[tree -> count].kinds_N == 0)    	// если у узла нет дочерних
	{
	  tree -> nodes[tree -> count].kinds_N = 1;        // количество дочерних узлов +1
	  tree -> nodes[tree -> count].left = tree -> nodes_N;	// указатель на левую дочку
	  tree -> nodes[tree -> nodes_N].parent = tree -> count;// указатель на родителя
	  tree -> count = tree -> nodes_N;            // переходим к дочке
	  tree -> nodes[tree -> count].type = type;        // устанавливаем тип узла
	  tree -> nodes[tree -> count].value = value;
	  tree -> nodes[tree -> count].kinds_N = 0;
	  tree -> nodes_N++;                	// общее количество узлов +1
	}
	else if (tree -> nodes[tree -> count].kinds_N == 1)    // если есть один дочерний
	{
	  tree -> nodes[tree -> count].kinds_N = 2;        // количество дочерних узлов +1
	  tree -> nodes[tree -> count].right = tree -> nodes_N;	// указатель на правую дочку
	  tree -> nodes[tree -> nodes_N].parent = tree -> count;// указатель на родителя
	  tree -> count = tree -> nodes_N;            // переходим к дочке
	  tree -> nodes[tree -> count].type = type;        // устанавливаем тип узла
	  tree -> nodes[tree -> count].value = value;
	  tree -> nodes[tree -> count].kinds_N = 0;
	  tree -> nodes_N++;                	// общее количество узлов +1
	}
	else if (tree -> nodes[tree -> count].kinds_N == 2)
	{
	  ;// выделяем память для массива индексов подузлов
	}
	return 0; 	// без ошибок
	
}
//==========================================================
// Переход к родительскому узлу AST - дерева 
//==========================================================
int ASTup(TASTtree *tree)
{
	tree -> count = tree -> nodes[tree -> count].parent;	// переходим к родительскому узлу
	return 0; 	// без ошибок
}
//==========================================================
// Вставка дополнительного узла AST - дерева 
// между текущим и родительским и переход к нему
//==========================================================
int ASTinsert(TASTtree *tree, int type)
{
	
	int temp = tree -> count;                //запоминаем текущий
	tree -> count = tree -> nodes[tree -> count].parent;	// переходим к родительскому узлу
	tree -> nodes[tree -> count].kinds_N--;
	ASTadd(tree, type, 0);
	tree -> nodes[tree -> count].kinds_N = 1;        // количество дочерних узлов +1
	tree -> nodes[tree -> count].left = temp;        // указатель на левую дочку
	tree -> nodes[temp].parent = tree -> count;
	
	return 0; 	// без ошибок
	
}

#endif	// ASTTREE_H

//******************************************************************
// Программа-калькулятор математических выражений
// Поддерживаются операции +,-,*,/, унарный минус, возведение в степень ^,  круглые скобки
//*******************************************************************



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <assert.h>
#include<Windows.h>

#include "ASTtree.h"

#define NUM    	-1 
#define PAR    	0 
#define NONE    1 
#define PLUS    2 
#define MINUS    3 
#define STAR    4 
#define SLASH    5 
#define UNARY_MINUS	6
#define POW    	7

int 	tok;    // тип токена
double 	tokval;    // числовое значение токена (если это число)
TASTtree ASTtree;
//==========================================================
// Вспомогательная функция. Используется для рисования дерева.
//==========================================================
void SetConsoleCursor(int x, int y)
{
	COORD position;
	HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);            // Получение дескриптора устройства стандартного вывода
	position.X = x;                                              // Установка координаты X
	position.Y = y;                                              // Установка координаты Y
	SetConsoleCursorPosition(hStdOut, position);
}


 

//===========================================================
// рисуем дерево
// рисует рекурсивно при каждом вызове по одному узлу
//=========================================================== 
void PrintTree (TASTnode node, int x, int y, int level)
{
	int delta = 24 / pow(1.73,level);
	SetConsoleCursor(x-1,y);
	switch (node.type)
	{
	  case NUM:
	    SetConsoleCursor(x-2,y);
    printf("[%.2g]",node.value);
	    break;
	  case PAR:
	    SetConsoleCursor(x-2,y);
    printf("[( )]");
	    break;
	  case NONE:
	    printf("[.]");
	    break;
	  case PLUS:
	    printf("[+]");
	    break;
	  case MINUS:
	  case UNARY_MINUS:
	    printf("[-]");
	    break;
	  case STAR:
	    printf("[*]");
	    break;
	  case SLASH:
	    printf("[/]");
	    break;
	  case POW:
	    printf("[^]");
	    break;
	  default:
	    
	    break;
	}
	if(node.kinds_N == 1){
    SetConsoleCursor(x,y+1);
    printf("|");
    SetConsoleCursor(x,y+2);
    printf("|");
    PrintTree(ASTtree.nodes[node.left], x, y+3, level);

	}
	else if(node.kinds_N == 2){
    SetConsoleCursor(x-delta,y+1);
    for (int i=0; i<= delta * 2 ;i++ )
    {
      printf("-");
    }
    SetConsoleCursor(x-delta,y+2);
    printf("|");
    SetConsoleCursor(x+delta,y+2);
    printf("|");
    PrintTree(ASTtree.nodes[node.left], x-delta, y+3, level+1);
    PrintTree(ASTtree.nodes[node.right], x+delta, y+3, level+1);

	} 	
	SetConsoleCursor(0,0);
    	

}
#define COUNT_NODE    ASTtree.nodes[ASTtree.count]	// текущий узел
#define PARENT_INDEX	COUNT_NODE.parent        // указатель на родительский узел
#define LEFT_INDEX    COUNT_NODE.left        	// указатель на левый дочерний узел
#define RIGHT_INDEX    COUNT_NODE.right        // указатель на правый дочерний узел
#define PARENT_NODE    ASTtree.nodes[PARENT_INDEX]    // родительский узел
#define RIGHT_INDEX    COUNT_NODE.right        // указатель на правый дочерний узел
//==========================================================
// маленький лексер
//==========================================================
int next() {
    for (;;) {
        int c = getchar();
        if (c == EOF || strchr("+-*/^()\n", c) != NULL) return tok = c;
        if (isspace(c)) continue;
        if (isdigit(c) || c == '.') {
            ungetc(c, stdin);
            scanf(" %lf", &tokval);
            return tok = 'n';
        }
        fprintf(stderr, "Bad character: %c\n", c); abort();
    }
}
//==========================================================
// Вспомогательная функция
//========================================================== 
void skip(int t) { assert(tok == t); next(); }

//==========================================================
// Предварительные обЪявления
//========================================================== 
double expr();
double factor();


//==========================================================
// Парсер состоит из нескольких фукций, вызываемых рекурсивно
//========================================================== 
// numpar ::= number | -factor |'(' expr ')'
double numpar() {
    if (tok == 'n') { 
    	double x = tokval; skip('n');
    	ASTadd(&ASTtree, NUM, tokval); 
    	return x; 
    	}
    if (tok == '-') {
    	skip('-'); 
    	ASTadd(&ASTtree, UNARY_MINUS,0); 
    	double x = - factor();   
    	return x; 
    	}
    skip('('); 
    ASTadd(&ASTtree, PAR,0);
    double x = expr(); 
    skip(')'); 
    while (PARENT_NODE.type > PAR)
        	{
        	  ASTup(&ASTtree);
        	}ASTup(&ASTtree);
     return x;
    //
} 
 
// factor ::= numpar | numpar '^' factor
double factor() {
    double x = numpar();
    if (tok == '^') { 
    	skip('^'); 
    	//while (ASTtree.nodes[ASTtree.nodes[ASTtree.count].parent].type > POW)
        while (PARENT_NODE.type > POW) // без макросов можно сойти с ума :)
        	{
        	  ASTup(&ASTtree);
        	}
        ASTinsert(&ASTtree, POW);
        x = pow(x, factor()); 
    }
    return x;
}
 
// term ::= factor | term '*' factor | term '/' factor
double term() {
    double x = factor();
    for (;;) {
        if (tok == '*') {
        	while (PARENT_NODE.type > STAR)
	        	{
	        	  ASTup(&ASTtree);
	        	} 
        	ASTinsert(&ASTtree, STAR);
        	skip('*'); x *= factor(); 
        	}
        else if (tok == '/') {
        	while (PARENT_NODE.type > STAR)
	        	{
	        	  ASTup(&ASTtree);
	        	}  
        	ASTinsert(&ASTtree, SLASH);
        	skip('/'); x /= factor(); 
        	}
        else {
        	//ASTup(&ASTtree); 
        	return x;}
    }
}
 
// expr ::= term | expr '+' term | expr '-' term
double expr() {
    	
    double x = term();
    for (;;) {
        if (tok == '+') { 
        	while (PARENT_NODE.type > PLUS)
	        	{
	        	  ASTup(&ASTtree);
	        	}
        	ASTinsert(&ASTtree, PLUS);
        	skip('+'); x += term(); 
        	}
        else if (tok == '-') { 
        	while (PARENT_NODE.type > PLUS)
	        	{
	        	  ASTup(&ASTtree);
	        	}
        	ASTinsert(&ASTtree, MINUS);
        	skip('-'); x -= term(); 
        	}
        else {
        	return x;
        }
    }
}
 
int main() {
	if (ASTinit (&ASTtree)) printf("Ошибка: >\n");
	ASTadd(&ASTtree, NONE,0); 
    
	printf("Введите математическое выражение: >\n");
    next();
    while (tok != EOF) {
    // разбор и вычисление
        if (tok == '\n') { skip('\n'); continue; }
        printf("%.9g\n", expr());
    	
    
	    PrintTree(ASTtree.nodes[0],60,8,0);    //рисуем дерево
	   // getchar();                //пауза
	    ASTtree.count = 0;            //имитируем очистку дерева
	    ASTtree.nodes_N = 0;
	    ASTadd(&ASTtree, NONE,0); 
	    
	   // system("cls");            	//очистка экрана
    printf("Введите математическое выражение: >\n"); 
    }
  
    ASTfree (&ASTtree);            	//освобождаем память под деревом
    return 0;
}