Лабы заочникам Яковлев / SiAOD(с++) / лаb4 / Unit1

//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <conio.h>
 
//---------------------------------------------------------------------------
 
#pragma argsused
 
 
using namespace std;
 
struct stek
{
  char data;
  struct stek *next;
};
 
int GetPriority(char a);
struct stek *GetObrPolsk(char inect[150]);//Получить постфиксную нотацию
struct stek *GetPrefics(char inect[150]);//Получаем префиксную нотацию
void AddElList(struct stek *p,char data);//Добавить в список элемент
void PrintStek(struct stek *p);//Вывод стэка
struct stek *AddElStek(struct stek *p, char data);//Добавить в стэк
struct stek *DelElStek(struct stek *p);//Удалить со стэка
 
int main()
{
  struct stek *head;
  head = (struct stek *)malloc(sizeof(struct stek));
  head->data='|';
  head->next=NULL;
  char inect[150];
  cout << "Vvedite formulu: \n";
  cin >> inect;
  head = GetObrPolsk(inect);
  cout << "Postfiksnoe predstavlenie: \n";
  PrintStek(head);
  cout << "Prefiksnoe predstavlenie: \n";
  head=GetPrefics(inect);
  PrintStek(head);
  getch();
  return 0;
}
 
struct stek *AddElStek(struct stek *p, char data)
{
//Создаём новый элемент, назначем его первым в списке, возвращаем
  struct stek *element;
  element = (struct stek *)malloc(sizeof(struct stek));
  element->data=data;
  element->next=p;
  return element;
}
 
void AddElList(struct stek *p, char data)
{
  struct stek *element;
  element = (struct stek *)malloc(sizeof(struct stek));
  element->next=NULL;
  element->data=data;
  //Если текущий элемент последний, то назначаем ему данные
  if ((p->data=='|')||(p->data==NULL))
  {
      p->data=data;
      p->next=NULL;
  }
  else
   {
       //Идём в конец списка
      while (p->next!=NULL)
        p=p->next;
      p->next=element;
   }
}
 
void PrintStek(struct stek *p)
{
  while (p!=NULL)//перебор всех элементов стэка
  {
    if (p->data!='|') cout << p->data;//Если не последний элемент, то вывести
    p=p->next;
  }
  cout << endl;
}
 
struct stek *DelElStek(struct stek *p)
{
    struct stek *element;
    element = (struct stek *)malloc(sizeof(struct stek));
    //Если мы находимся в конце списка
    if (p->next==NULL)
    {
        p->data='|';//Обозначаем текущий элемент последним
        return p;
    }
    else
    {//Иначе переходим на следующий элемент
      element = p->next;
      free(p);//Освобождаем память
      return element;
    }
}
 
struct stek *GetObrPolsk(char inect[150])
{
  struct stek *list;
  list = (struct stek *)malloc(sizeof(struct stek));
  list->data='|';
  list->next=NULL;
  struct stek *ste;
  ste = (struct stek *)malloc(sizeof(struct stek));
  //Внесение в стэк точки выхода
  ste->data='|';
  ste->next=NULL;
  int i=0;
  while (i!=strlen(inect))//Пока не дошли до конца строки
  {
    if (inect[i] >= 'a' && inect[i] <= 'z')//Если встретили символ от a до z
      AddElList(list,inect[i]);//Заносим в результирующий  список
    else if (GetPriority(inect[i])==1) //Если встретили открывающую скобку, заносим её в стэк знаков
      ste=AddElStek(ste,inect[i]);
      else if ((GetPriority(inect[i])!=0) && (GetPriority(inect[i])!=1) ) // иначе, если это не скобка и математический символ
        if ((GetPriority(ste->data)<GetPriority(inect[i])) || (ste->next==NULL))
            //Если последний добавленный знак, по приоритету меньше, или следующий элемент пустой, заносим текущий знак в стэк
          ste=AddElStek(ste,inect[i]);
        else
            //Иначе
          {
              //Пока преоритеты в стэке больше либо равны переданного, освобождаем стэк
              //И заносим в результирующий список
             while ((GetPriority(ste->data))>=(GetPriority(inect[i])))
             {
               AddElList(list,ste->data);
               ste=DelElStek(ste);
             }
             ste=AddElStek(ste,inect[i]);
          }
     if (inect[i]==')')//Если встретили закрывающую скобку
     {
         //То освобождаем стэк и заносим в результрующий список все элементы до открывающейся скобки
       while ( ste->data!='(' )
       {
         AddElList(list,ste->data);
         ste=DelElStek(ste);
       }
       ste=DelElStek(ste);
     }
    i++;
  }
  //По прохождению всех символов, осовобождаем стэк и заносим в результирующий список
  while (ste->next!=NULL)
  {
    AddElList(list,ste->data);
    ste=DelElStek(ste);
  }
  //Отдаём список
  return list;
}
 
struct stek *GetPrefics(char inect[150])
{
  struct stek *list;
  list = (struct stek *)malloc(sizeof(struct stek));
  list->data='|';
  list->next=NULL;
  char buff[150];//Строка для переворота
  for (int i=strlen(inect)-1; i>=0; i--)
  {
      //Записываем все символы с конца в начало, меняем открывающийся скобки на закрывающиеся, и наоборот
    if (inect[i]=='(')
      buff[strlen(inect)-i-1]=')';
    else
    if (inect[i]==')')
      buff[strlen(inect)-i-1]='(';
    else buff[strlen(inect)-i-1]=inect[i];
  }
  //Получаем применяем постфиксный алгоритм
  list=GetObrPolsk(buff);
  struct stek *l;
  l = (struct stek *)malloc(sizeof(struct stek));
  l->data='|';
  l->next=NULL;
  //Переворачиваем результат
  while (list!=NULL)
  {
    l=AddElStek(l,list->data);
    list=list->next;
  }
  //Возвращаем
  return l;
}
 
int GetPriority(char a)
{
  switch(a)
  {
    case '^': return 4;
    case '*': return 3;
    case '/': return 3;
    case '-': return 2;
    case '+': return 2;
    case '(': return 1;
    default:  return 0;
  }
}
 
//---------------------------------------------------------------------------