Проектная спецификация
.
Для реализации данной программы необходимо использовать за шаблон LISP-подобный язык. Формат перевода функции должен быть в виде:
#(имя_функции, параметр1, …)’
Символ # означает вызов функции, в скобках первым параметром указывается имя вызываемой функции, после чего следует список ее параметров. Апостроф в конце строки означает конец предложения. В качестве параметров выступают имена переменных, числа и другие вызовы функций.
В программе должно быть реализовано 2 основных модуля: модуль проверки и модуль трансляции.
Исходные выражения в инфиксной форме принимаются программой построчно через stdin в строчную переменную.
Далее необходимо разбить каждое строку на лексемы, записать каждую в дек и проверить коррекцию этих лексем. Так же необходимо проверить коррекцию последовательности самих этих лексем. Целесообразнее делать проверку на основе конечного автомата Мура.
В случае удачной проверки, программа передает данный дек в модуль трансляции выражений. В данном модуле, для перевода в префиксную систему, целесообразнее сделать реверсию математического выражения, перевести выражение в постфиксную форму (необходимо учитывать приоритеты знаков), а далее снова использовать реверсию дека.
4+5*6
6*5+4
4(56*)+
(*65)4+
Так же целесообразно для перевода выражения в постфиксную систему завести отдельны стек для знаков, где будут определены приоритеты каждого знака.
После окончания перевода дека и его повторной реверсии, необходимо передать дек в функцию расстановки скобок и метасимволов.
Далее необходимо вывести полученное выражение в stdout и удалить рабочий дек.
Эксплуатационная документация
Указания для работы с программой:
1) Для начала работы нажмите на файл zapusk.bat.
2) Перед вами высветится черное консольное окно с надписью:
«Введите выражение. Максимальная длина 1000 символом».
3) В данное окно введите Ваше алгебраическое выражение, по описанным выше правилам (см. Функциональная спецификация) и нажмите Enter.
4) В случае, если программа выдает ошибку, перепроверьте правильность введенных данных.
Если ошибка «Проверьте баланс скобок», то следует проверить количество открывающихся и закрывающихся скобок
Если ошибка «Ошибка синтаксиса», то следует перепроверить правильность введенных переменных, знаков, точек и тд(см. Функциональная спецификация)
Далее следует повторить ввод выражения, исправив ошибки.
5) В случае, если выражение было введено правильно, то программа выведет на экран выражение в требуемой форме.
Если необходимо завершить работу программы, то нажмите крестик в левом верхнем углу.
Проектная документация
В данной программе используются следующие методы:
int main()
Рабочая функция, в которой происходит принятия потока в stdin построчно, считывает из нее функция cin.getline() в переменную string. Далее идет вызов функций: удаления пробелов(delite_space()), проверка баланса скобок(string_work()). В случае если проверка пройдена успешно, main передает строку в функцию работы со строкой (string_work()). В случае завершения работы, функция возвращает 0.
char *delite_space(const char *str)
В данной функции происходит удаление всех пробелов.
Создается строка(char *result), в которую копируется из string все, кроме пробелов. В результате работы функции возвращается строка result.
int bkt(char *str)
В данном методе идет подсчет баланса скобок.
В результате работы программы возвращается либо перевес скобок, либо 0 (в случае, если количество открывающихся скобок равно количеству открывающихся). В случае, если возвращаемое значение не равно нулю, то выдается сообщение об ошибке.
int string_work(char *str)
В данной функции идет работа со строкой. Сначала вызывается функции проверки синтаксиса (check_syntax()). В случае, если проверка не пройдена, выдается сообщение об ошибке. Далее вызывается функция трансляции дека (translation() ) и вывод преобразованного выражения.
int check_syntax(char *str, deque <char*> & deq)
Функция проверяет, какого вида у нас выражение (a=b+c или b+c ). Далее она передает полученную строку во вторую часть проверки(proverka()), которая в свою очередь возвращает результат работы (true или false).
int proverka(char *str, int i, deque <char*> & deq )
В данном методе идет вызов функции деления строки на лексемы и проверка коррекции последовательности этих лексем. Выполнено на основе автомата Мура. Возвращает значения SUCCESS или FAIL.
void tokens(char *str, int k, deque <char*> & target )
В данной функции идет деление строки на лексемы и запись каждой отдельной лексемы в дек. Возвращает полученный дек.
int avtomat(char *str)
Выделяет проверку коррекции каждого отдельного слова. В качестве поступающего значения – каждый элемент дека с лексемами. Возвращает вид данных лексемы(переменная, число, арифметические знаки, скобки)
void translation(deque <char*> & deq, int st)
В этом методе последовательно вызываются функции для работы с полученным деком: реверсия, перевод в постфиксную форму, расстановка скобок и служебных символов.
void reverse(deque <char*> & deq)
Данная функция инвертирует дек (записывает наоборот) .
void form_postfix(deque <char*> & deq)
В этой функции происходит перевод инфиксного выражения в постфиксную. Заводится результирующий дек и отдельный дек для знаков. Далее все записывается в результирующий дек с учетом приоритетов операций.
void converter(deque <char*> & deq, int st)
В данном методе происходит правильная расстановка скобок, запятых и служебных символов. Расстановка идет с учетом того, какого вида является выражение (a=b+c или b+c ).
string rus(char s[ ])
Данная функция выполняет перевод строки Windows в Dos для удобства общения с пользователем.
Приложение 1. Текст программы.
#include <conio.h>
#include <iostream.h>
#include <string.h>
#include <deque.h>
/*Курсовая работа
студента: Чикина Анна
группа: ИТП-1-10
вариант: LISP-интерпретатор, вариант 1 */
enum {
START=0,
//конечные состояния
VARIABLE=1,
CIFRA=2,
MINUS=3,
PLUS=4,
UMN=5,
DEL=6,
OS=7,
ZS=8,
SPACE=32,
ZNAK=33,
SUCCESS=100,
FAIL=-1,
TOCHKA=19,
CIFRA_TOCHKA=20,
//переходные состояния
VARIABLE1=11,
CIFRA1=12,
MINUS1=13,
PLUS1=14,
UMN1=15,
DEL1=16,
OS1=17,
ZS1=18,
//вспомогательные состояния
S1=30,
S2=31,
WITHOUT=40,
//максимальная длина строки
max_str=1000,
//максимальная длина 1 переменной
max_p=16
};
string rus(char s[ ]) //переводит кодировку выводимой строки Windows в Dos
{
string t;
int i=0;
t=s;
while (s[i]!=0)
{
if(s[i]>='А'&& s[i]<='п' ) t[i]-=64;
if(s[i]>='р'&& s[i]<='я' ) t[i]-=16;
if(s[i]=='Ё' )t[i]=240;
if(s[i]=='ё' ) t[i]=241;
i++;
}
return t;
}
//удаление лишних пробелов
char *delite_space(const char *str)
{
char *result = new char [max_str];
int i = 0, j = 0;
while (str[i] != '\0')
{
if (str[i] != ' ')
{
result[j] = str[i];
j++;
}
i++;
}
result[j] = '\0';
return result;
}
//проверка баланса скобок
int bkt(char *str)
{
int i=0;
int count=0; // счетчик скобок
while(str[i]!='\0')
{
if(str[i]=='(')
count++;
if(str[i]==')')
{
count--;
if (count < 0)
return 1;
}
i++;
}
return count;
}
//выделение лексемы и запись ее в дек.
void tokens(char *str, int k, deque <char*> & target )
{
int i=k;
while(str[i]!='\0')
{
char *slovo = new char[max_p];
int j=0;
if(str[i]=='(' && str[i+1]=='-')
{
i++;
while (str[i]!=')' )
{
slovo[j]=str[i];
i++;
j++;
}
slovo[j]='\0';
i++;
}
else
{
if( isalpha(str[i]) || isdigit(str[i]) )
{
while( isalpha(str[i]) || isdigit(str[i]) ||
str[i]=='.' )
{
slovo[j]=str[i];
i++;
j++;
}
slovo[j]='\0';
}
else
{
slovo[j]=str[i];
slovo[j+1]='\0';
i++;
}
}
target.push_back(slovo);
}
target.push_back("\0");
}
//функция проверяет коррекцию каждого отдельного слова
int avtomat(char *str)
{
int state=START;
int idx=0;
while(state!=CIFRA && state!=VARIABLE && state!=MINUS &&
state!=PLUS && state!=UMN && state!=DEL &&
state!=OS && state!=ZS && state!=FAIL && state!=SUCCESS)
{
switch(state)
{
case START:
state=(isdigit(str[idx]))? CIFRA1:
(isalpha(str[idx]))? VARIABLE1:
(str[idx]=='-')? MINUS1:
(str[idx]=='+')? PLUS1:
(str[idx]=='*')? UMN1:
(str[idx]=='/')? DEL1:
(str[idx]=='(')? OS1:
(str[idx]==')')? ZS1:
(str[idx]=='\0' || str[idx]=='\n')? SUCCESS: FAIL;
break;
case CIFRA1:
state=(isdigit(str[idx]))? CIFRA1:
(str[idx]=='.')? TOCHKA:
(str[idx]=='\0' || str[idx]=='\n')? CIFRA: FAIL;
break;
case VARIABLE1:
state=(isalpha(str[idx]))? VARIABLE1:
(str[idx]=='\0' || str[idx]=='\n')? VARIABLE: FAIL;
break;
case MINUS1:
state=(isdigit(str[idx]))? CIFRA1:
(isalpha(str[idx]))? VARIABLE1:
(str[idx]=='\0' || str[idx]=='\n')? MINUS: FAIL;
break;
case PLUS1:
state=(str[idx]=='\0' || str[idx]=='\n')? PLUS: FAIL;
break;
case UMN1:
state=(str[idx]=='\0' || str[idx]=='\n')? UMN: FAIL;
break;
case DEL1:
state=(str[idx]=='\0' || str[idx]=='\n')? DEL: FAIL;
break;
case OS1:
state=(str[idx]=='\0' || str[idx]=='\n')? OS: FAIL;
break;
case ZS1:
state=(str[idx]=='\0' || str[idx]=='\n')? ZS: FAIL;
break;
case TOCHKA:
state=(isdigit(str[idx]))? CIFRA_TOCHKA: FAIL;
break;
case CIFRA_TOCHKA:
state=(isdigit(str[idx]))? CIFRA_TOCHKA:
state=(str[idx]=='\0' || str[idx]=='\n')? CIFRA: FAIL;
break;
}
idx++;
}
return state;
}
/*в функции идет вызов функции деления строки на лексемы,
и проверка правильной последовательности этих лексем */
int proverka(char *str, int i, deque <char*> & deq )
{
char *st=new char[max_p];
int s;
tokens(str, i, deq); //деление на лексемы
int j=0;
int state = START;
//в st хранится слово, в s - результат проверки слова
while(state!=SUCCESS && state!=FAIL)
{
if(j>deq.size())
{
state=FAIL;
}
else
{
st = deq[j];
s=avtomat(st); //проверка каждой лексемы
switch(state)
{
case START:
case OS:
state=(s==CIFRA)? CIFRA1:
(s==VARIABLE)? VARIABLE1:
(s==OS)? OS: FAIL;
break;
case CIFRA1:
case VARIABLE1:
state=(s==MINUS || s==PLUS ||
s==UMN || s==DEL )? ZNAK:
(s==SUCCESS)? SUCCESS: FAIL;
break;
case ZNAK:
state=(s==CIFRA)? CIFRA:
(s==VARIABLE)? VARIABLE:
(s==OS)? OS: FAIL;
break;
case CIFRA:
case VARIABLE:
case ZS:
state=(s==MINUS || s==PLUS ||
s==UMN || s==DEL )? ZNAK:
(s==ZS)? ZS:
(s==SUCCESS)? SUCCESS: FAIL;
break;
}
j++;
}
}
return state;
}
/*функция проверяет, какого вида выражение:
a=b+c или b+c и т.д. */
int check_syntax(char *str, deque <char*> & deq)
{
//проверка начала синтаксиса:
int state=START;
int idx=0;
while(state!=S1 && state!=WITHOUT)
{
switch(state)
{
case START:
state=(isalpha(str[idx]))? VARIABLE: WITHOUT;
break;
case VARIABLE:
state=(isalpha(str[idx]))? VARIABLE:
(str[idx]=='=' && str[idx+1]!='=')? S1 : WITHOUT;
break;
}
idx++;
}
//вызов второй части проверки
if(state == S1)
{ //если выражение вида: a=b+c
state=proverka(str, idx, deq);
}
if(state == WITHOUT)
{ //если выражение вида: b+c
idx=0;
state=proverka(str, idx, deq);
if(state!=FAIL)
state=WITHOUT;
}
return state;
}
//функция реверсии записи
void reverse(deque <char*> & deq)
{
deque <char*> d(deq);
int j=0;
for (int i=deq.size()-1; i>=0; i--)
{
if (deq[i][0]=='(')
d[j]=")";
else
if (deq[i][0]==')')
d[j]="(";
else
d[j]=deq[i];
j++;
}
d.push_back("%");
d.pop_front(); //удалили первый элемент, т.к. там был "\0"
deq=d;
d.clear();
}
//запись в постфиксную систему
void form_postfix(deque <char*> & deq)
{
deque <char*> result;
deque <char*> znaki;
char *st = new char;
int i=0;
znaki.push_back("%");
while(deq[i][0]!='%')
{
//если в деке открывающаяся скобка
if(deq[i][0]=='(')
znaki.push_back("(");
else //если в деке закрывающаяся скобка
if(deq[i][0]==')')
{
st=znaki.back();
znaki.pop_back();
while(st[0]!='(')
{
result.push_back(st);
st=znaki.back();
znaki.pop_back();
}
}
else //если в деке арифметические знаки + или -
if( (deq[i][0]=='+' || deq[i][0]=='-') && deq[i][1]== '\0' )
{
st=znaki.back();
znaki.pop_back();
if(st[0]=='%'||st[0]=='(')
{
znaki.push_back(st);
znaki.push_back(deq[i]);
}
else
if (deq[i][0]=='+' || deq[i][0]=='-'|| deq[i][0]=='*' || deq[i][0]=='/')
{
result.push_back(st);
znaki.push_back(deq[i]);
}
}
else //если в деке аривметические знаки * или /
if(deq[i][0]=='*'|| deq[i][0]=='/')
{
st=znaki.back();
znaki.pop_back();
if ( st[0]=='%'||st[0]=='('||st[0]=='+'||st[0]=='-' )
{
znaki.push_back(st);
znaki.push_back(deq[i]);
}
if (st[0]=='*'||st[0]=='/')
{
if(st[0] == '*' && deq[i][0] == '/')
{
znaki.push_back(st);
znaki.push_back(deq[i]);
}
else
{
result.push_back(st);
znaki.push_back(deq[i]);
}
}
}
else
result.push_back(deq[i]);
i++;
}
st=znaki.back();
znaki.pop_back();
//кладем в резуьтивный стек оставшиеся знаки
while (st[0]!='%')
{
result.push_back(st);
st=znaki.back();
znaki.pop_back();
}
deq=result;
result.clear();
znaki.clear();
}
//функция расставляет в правильном порядке скобки, запятые и #
void converter(deque <char*> & deq, int st)
{
deq.push_front("%"); // добавили в начало знак конца
int i=deq.size()-1;
deque <char*> d;
int state; // если S1 - то первый параметр функции, если S2 – то второй
int brk; // количество открытых скобок
if(st==WITHOUT)
{
state = S1;
brk = 0;
}
else
{
state = S2;
brk = 1;
}
while (deq[i][0]!='%')
{
if ( (deq[i][0]=='+' || deq[i][0]=='-' ||
deq[i][0]=='*' || deq[i][0]=='/') && deq[i][1]=='\0')
{
if (state == S2)
d.push_back(",");
d.push_back("#");
d.push_back("(");
d.push_back(deq[i]);
d.push_back(",");
state = S1;
brk++;
}
else
{
if (state == S2)
{
d.push_back(",");
d.push_back(deq[i]);
d.push_back(")");
brk--;
}
else if (state == S1)
{
d.push_back(deq[i]);
state = S2;
}
}
i--;
}
while (brk>0)
{
d.push_back(")");
brk--;
}
deq=d;
d.clear();
}
//последовательно вызываются функции
void translation(deque <char*> & deq, int st)
{
deque <char*> d(deq); //рабочий дек
reverse(d); //запись наоборот
form_postfix(d); //перевод в постфиксную систему
converter(d, st); //расстановка скобок
deq = d;
d.clear();
}
//функция работы со строкой
int string_work(char *str)
{
deque <char*> deq;
int state = check_syntax(str, deq); //вызываем функцию проверки синтаксиса
if(state==FAIL)
{
cerr<<rus("Ошибка синтаксиса \n");
system ("PAUSE");
}
else
{
translation(deq,state); //вызываем функцию трансляции дека
if(state!=WITHOUT)
{ // записали имя переменной слева от знака присвоения
char *st = new char [max_p];
int i = 0;
while (str[i] != '=')
{
st[i] = str[i];
i++;
} st[i] = '\0';
//дописали в начало очереди начало выходной строки вида #(=,a
deq.push_front(st);
deq.push_front(","); //добавили остальные знаки
deq.push_front("=");
deq.push_front("(");
deq.push_front("#");
}
//вывод дека
deq.push_back("'");
while (!deq.empty())
{
cout << deq[0];
deq.pop_front();
}
}
cout<<'\n';
deq.clear();
return 0;
}
int main()
{
char *string = new char[max_str];
cout<<rus("Введите выражение. Максимальная длина 1000 символов \n");
while(!feof(stdin))
{
cin.getline(string,max_str,'\n');
if(strcmpi(string, "\0")!=0)
{
string=delite_space(string); //удаление пробелов
if(bkt(string)!=0)
{
cerr<<rus("проверьте баланс скобок \n");
system ("PAUSE");
}
else
{
string_work(string);
cout << '\n';
}
}
}
return 0;
}