Задание 4 Использование стеков для построения различных форм представления выражений
Текст задания
Используя стек, реализовать алгоритм преобразования алгебраического выражения из инфиксной формы записи в постфиксную форму представления.
Используя стек, реализовать алгоритм преобразования алгебраического выражения из инфиксной формы записи в префиксную форму представления.
Для обоих алгоритмов предусмотреть вхождение операций с различными приоритетами, а также наличие скобок в инфиксных выражениях.
Реализация программы
#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;
}
}
Контрольные вопросы:
Дайте определение абстрактному типу данных «стек»;
Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top).
Перечислите основные операторы, которые определены для работы со стеком;
MAKENULL(S). Делает стек пустым.
TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1.
POP(S). Удаляет элемент из вершины стека (выталкивает из стека).
PUSH(x, S). Вставляет элемент х в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной и т.д.
EMPTY (S). Эта функция возвращает значение true (истина), если список S пустой и значение false (ложь) – в противном случае.
Назовите основное преимущество обратной польской записи перед обычной записью выражений со скобками;
Основное преимущество обратной польской записи перед обычной записью выражений со скобками: выражение можно вычислить в процессе однократного просмотра слева направо.
Каким образом используется стек для преобразования выражений из одной формы записи в другую?
Алгоритм преобразования:
1. В стек помещается признак пустого стека.
2. Значение приоритета очередного входного символа сравнивается с приоритетом верхнего элемента стека.
3. Если приоритет символа больше приоритета верхнего элемента стека, то символ помещается в стек, выбирается следующий входной символ.
4. Если приоритет входного символа меньше или равен приоритету верхнего элемента стека, то этот элемент удаляется из стека и помещается в формируемую строку, после чего сравнивается приоритеты очередного символа и нового верхнего символа.
Каждый раз при изменении обратной польской записи модифицируется ранг результирующего выражения.