Постановка задачи
Разработать программу для трансляции выражений в ПОЛИЗ логического выражения в языке Pascal.
Таблица приоритетов.
Метод построения ПОЛИЗА основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается ПОЛИЗ. При этом каждому ограничителю, входящему в выражение, присваивается приоритет. Для знаков операции приоритеты возрастают в порядке, обратном старшинству операций. Скобки имеют низший приоритет.
В логических выражениях языка Pascal приоритеты у операций следующие:
1. not
2. *, /, and
3. +, -, or, xor
4. =, <>, <, >,<=, >=
Для программы приоритеты у знаков будут следующие:
0. (
1. )
2. =, <>, <, >, <=, >=
3. +, -, or, xor
4. *, /, and
5. not
Описание входных и выходных данных
Входными данными для программы является строка, содержащая логическое выражение (оно должно быть верным, т.к. проверка на ошибки не производится). Во входной строке все операнды могут представлять большими буквами латинского алфавита и цифрами (длина каждого операнда один символ), а операции кодируются следующим образом:
| Операция | Код |
| + | + |
| - | - |
| * | * |
| / | / |
| = | = |
| <>
| ! |
| <
| <
|
| >
| >
|
| <= | l |
| >= | g |
| not | n |
| and | a |
| or | o |
| xor | x |
Также в программе применяется внутреннее кодирование символов для удобства построения ПОЛИЗА. Кодирование следующее: если символ операнд, то он не кодируется (остаётся таким же), если символ знак операции, то первый бит его кода принимает значение ‘1’, следующие три бита содержат приоритет, а последние четыре номер в массиве знаков операции. (const char ChInSt[]={'(', ')', 'n', '*', '/', 'a', '+', '-', 'o', 'x', '=', '!', '<', '>', 'g', 'l', '#'};)
Для работы используется стек с элементами типа char.
Описание алгоритма
Арифметическое или логическое выражение рассматривается как входная строка символов. Входная строка рассматривается слева направо. Операнды переписываются в выходную строку, а знаки операций помещаются вначале в стек операций.
Если приоритет входного знака равен нулю или меньше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека "выталкивается" и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека.
Особенности имеет лишь обработка скобок. Открывающаяся круглая скобка, имеющая "особый" приоритет нуль, просто записывается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки.
Закрывающая скобка имеет приоритет 1, не превосходящий приоритет любой операции. Поэтому появление закрывающей скобки вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся.
После просмотра всех символов входной cтроки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.
Тестовые примеры
1. Входная строка – “A+B”
Result:
AB+
2. Входная строка – “A+B!3”
Result:
AB+3!
3. Входная строка – “A+B=3*ZaC!2”
Result:
AB+3Z*Ca=2!
4. Входная строка – “A*(B+C)<7”
Result:
ABC+*7<
5. Входная строка – “A*(B-C/(L-9))gM”
Result:
ABCL9-/-*Mg
Текст программы
stack.h
template <class T> class Stack;
template <class T>
class Node
{
friend class Stack<T>;
private:
T *node;
Node<T> *p;
public:
Node (const T &t);
~Node();
};
template <class T>
class Stack
{
private:
Node<T> *lp;
public:
Stack();
~Stack();
void Push(T);
bool Pop(T *);
};
stack.cpp
//---------------------------------------------------------------------------
#include "stack.h"
#include <stddef.h>
//---------------------------------------------------------------------------
template <class T>
Node<T>::Node (const T &t): node(new T(t)), p(NULL){}
//---------------------------------------------------------------------------
template <class T>
Node<T>::~Node()
{
if (p)
delete p;
delete node;
}
//---------------------------------------------------------------------------
template <class T>
Stack<T>::Stack(): lp(NULL){}
//---------------------------------------------------------------------------
template <class T>
Stack<T>::~Stack()
{
if (lp)
delete lp;
}
//---------------------------------------------------------------------------
template <class T>
void Stack<T>::Push(T n)
{
Node<T> *new_node=new Node<T>(n);
new_node->p=lp;
lp=new_node;
}
//---------------------------------------------------------------------------
template <class T>
bool Stack<T>::Pop(T *n)
{
if (lp)
{
*n=*(lp->node);
Node<T> *del_node=lp;
lp=lp->p;
del_node->p=NULL;
delete del_node;
}
else return 0;
return 1;
}
//---------------------------------------------------------------------------
lab5.cpp
//---------------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
//---------------------------------------------------------------------------
#include <iostream.h>
#include <conio.h>
#include "stack.cpp"
#include <string.h>
//---------------------------------------------------------------------------
const char ChInSt[]={'(', ')', 'n', '*', '/', 'a', '+', '-', 'o', 'x', '=', '!', '<', '>', 'g', 'l', '#'};
char *POLIZ(char *);
char *Code(char *);
char *Decode(char *);
//---------------------------------------------------------------------------
void main()
{
clrscr();
char st[200], *resP, *res;
cout<<"Input string"<<endl;
cin>>st;
res=Code(st);
resP=POLIZ(res);
delete res;
res=Decode(resP);
cout<<"Result:"<<endl<<res<<endl;
getch();
delete res, resP;
}
//---------------------------------------------------------------------------
char *POLIZ(char *st)
{
Stack<char> s;
char n;
int prior, j=0;
char *res=new char[strlen(st)];
for (unsigned int i=0; i<strlen(st); i++)
{
if (!(st[i]&0x80))
{
res[j++]=st[i];
continue;
}
if (st[i]&0x0F)
{
prior=st[i]&0x70;
while (s.Pop(&n))
if ((n&0x70)>=prior)
res[j++]=n;
else
{
if (prior!=0x10)
s.Push(n);
break;
}
}
if (prior!=0x10)
s.Push(st[i]);
}
while (s.Pop(&n))
res[j++]=n;
res[j]=0;
return res;
}
//---------------------------------------------------------------------------
char *Code(char *st)
{
char *res=new char[strlen(st)+1];
strnset(res, 0, strlen(st)+1);
int j;
for (unsigned int i=0; i<strlen(st); i++)
{
for (j=0; j<17; j++)
if (st[i]==ChInSt[j])
break;
switch (j)
{
case 0: res[i]=0x80; break;
case 1: res[i]=j+0x90; break;
case 2: res[i]=j+0xD0; break;
case 3: case 4: case 5: res[i]=j+0xC0; break;
case 6: case 7: case 8: case 9: res[i]=j+0xB0; break;
case 10: case 11: case 12: case 13: case 14: case 15: res[i]=j+0xA0; break;
case 17: res[i]=st[i];
}
}
return res;
}
//---------------------------------------------------------------------------
char *Decode(char *st)
{
char *res=new char[strlen(st)+1];
for (unsigned int i=0; i<strlen(st); i++)
{
if (st[i]&0x80)
res[i]=ChInSt[st[i]&0x0F];
else res[i]=st[i];
}
res[strlen(st)]=0;
return res;
}
//---------------------------------------------------------------------------
0 коммент.:
Отправить комментарий