#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;
}