Преобразовать математическое выражение в его польскую запись.
(при построении математических выражений допустимы использования операций: +,-,*,/,^,% , круглых скобок, целых чисел, десятичных чисел, переменных с именами начинающимися на букву или знак "_").
АЛГОРИТМ:
Ввести строку, удалить из нее все пробелы, проверить(есть ли в конце "=", не начинается ли на операцию или точку, проверить баланс скобок, не стоит ли в одном числе две запятых и т.п.).
Преобразовать полученную строку в польскую запись на основании следующих правил:
1) Рассматривается исходная стpока символов слева направо, операнды
переписываются в выходную стpоку, а знаки операций заносятся в стек на
основе следующих соображений:
2) если очередной символ из исходной стpоки есть открывающая скобка, то он
проталкивается в стек;
3) если стек пуст, то операция из входной стpоки переписывается в стек;
4) закрывающая круглая скобка выталкивает все операции из стека до ближайшей
открывающей скобки, сами скобки в выходную стpоку не переписываются, а
уничтожают дpуг дpуга.
5) операция выталкивает из стека все операции с большим или равным
приоритетом в выходную стpоку.
#include <STDIO.H>
#include <IOSTREAM.H>
#include <CONIO.H>
#include <STDLIB.H>
class BoxLIFO
{
public:
BoxLIFO();
char pop(void); //достает из стека
void push(char); //помещает в стек
int getcount() const; //количество объектов класса
char getsteck();
~BoxLIFO();
private:
struct steck{
char c;
steck* next;
};
steck *Head; //указывает на вершину стека
static int count; //количество объектов класса
};//end class BoxLIFO
int BoxLIFO::count=0;
//BoxLIFO function
BoxLIFO::BoxLIFO(){
Head=NULL;
};
void BoxLIFO::push(char cC){
steck* cX=new steck;
(*cX).c=cC;
(*cX).next=Head;
Head=cX;
count++;
};//end push()
char BoxLIFO::pop(void){
if(count==0)
return 0;
char x=Head->c;
steck* y=Head->next;
delete Head;
Head=y;
count--;
return x;
};//end pop()
int BoxLIFO::getcount() const{
return count;
};//end getcount()
char BoxLIFO::getsteck() const{
return Head->c;
};//end getsteck()
BoxLIFO::~BoxLIFO(){
while( getcount() ) pop();
};
//end BoxLIFO function
void PolskZapis(char*,char*);//Преобразует в польскую запись
int prior(const char*); //Возвращает приоритет операции
int proverka(char*); //Проверяет является ли введенная строка математическим выражением
int delprobel(char*); //Удаляет все пробелы из строки
char kod(char); /*Возвращает "f" если на входе цифра, "l"-буква или "_",
o-операция,"."-".","("-"(",")"-")","="-"=","m"-любой другой символ отличный от предыдущих*/
int dlstr(char*); //Подсчитывает длину строки
void main(void){//----------------------------------------------------------
const int N=256;
char cInPutString[N],cOutPutString[N];
for(int i=0;i<N;i++)cInPutString[i]=cOutPutString[i]=0;//обнуление строк
PolskZapis( cInPutString, cOutPutString);
cout<<cOutPutString<<"\n";
getch();
};//end main----------------------------------------------------------------
void PolskZapis(char* cInPutString,char* cOutPutString){ //BEGIN PolskZapis
BoxLIFO stek;
int i=0,j=0,k,cQuantityEquality=0,iLeft=0,iRight=0;
int n=dlstr(cOutPutString);
for(i=n;i>0;i--) cOutPutString[i]=0;
//Ввод строки и ее проверка
while(cQuantityEquality!=1){
for(i=n;i>0;i--)cInPutString[i]=0;
while ((cInPutString[i] = getchar()) != '\n') i++;
cInPutString[i]=0;
i=delprobel(cInPutString);
cout<<cInPutString<<"-bez probelov\n";
cQuantityEquality=proverka(cInPutString);
};
/*
1) Рассматривается исходная стpока символов слева направо, операнды
переписываются в выходную стpоку, а знаки операций заносятся в стек на
основе следующих соображений:
2) если очередной символ из исходной стpоки есть открывающая скобка, то он
проталкивается в стек;
3) если стек пуст, то операция из входной стpоки переписывается в стек;
4) закрывающая круглая скобка выталкивает все операции из стека до ближайшей
открывающей скобки, сами скобки в выходную стpоку не переписываются, а
уничтожают дpуг дpуга.
5) операция выталкивает из стека все операции с большим или равным
приоритетом в выходную стpоку;
*/
char NextChar='a',cChar='a';
i=j=k=0;
NextChar=cInPutString[i];
while(NextChar!='='){
if/*0*/(NextChar==' '){
}//end if 0
else/*0*/{
if/*1*/( 'l'==kod(NextChar)||'f'==kod(NextChar)||'.'==kod(NextChar) ){
cOutPutString[j]=NextChar;j++;
k++;
}//end if 1
else/*1*/{
if(k){
cOutPutString[j]=' ';
j++;
};
k=0;
if/*2*/(NextChar=='('){
stek.push(NextChar);
}//end if 2
else/*2*/{
if/*3*/(!stek.getcount()){
stek.push(NextChar);
}//end if 3
else/*3*/{
if/*4*/(NextChar==')'){
while( '('!=( cChar=stek.pop() ) ){
if( !( stek.getcount() )&&'o'==kod(cChar) ){
cOutPutString[j]=' ';j++;
cOutPutString[j]=cChar;j++;
}else{
cOutPutString[j]=cChar;j++;
};
};//end while
}//end if 4
else/*4*/{
iLeft=prior(&NextChar);
cChar=stek.pop();
iRight=prior(&cChar);
while((iLeft<=iRight)&&(stek.getcount())){
cOutPutString[j]=cChar;j++;
cOutPutString[j]=' ';j++;
cChar=stek.pop();
iRight=prior(&cChar);
}//end while
if/*5*/(iLeft<=iRight){
cOutPutString[j]=cChar;j++;
cOutPutString[j]=' ';j++;
}//end if 5
else/*5*/{
stek.push(cChar);
};//end else 5
stek.push(NextChar);
};//end else 4
};//end else 3
};//end else 2
};//end else 1
};//end else 0
i++;
NextChar=cInPutString[i];
};//end while
while(stek.getcount()){
cChar=stek.pop();
if( !( stek.getcount() )&&'o'==kod(cChar) ){
cOutPutString[j]=' ';j++;
cOutPutString[j]=cChar;j++;
}else{
cOutPutString[j]=cChar;j++;
};
};//end while
cOutPutString[j]=' ';j++;
cOutPutString[j]='=';
}//end PolskZapis--------------------------------------------------------
int prior(const char* a){
switch (*a){
case '(': return 0;
case ')': return 0;
case '+': return 2;
case '-': return 2;
case '*': return 3;
case '/': return 3;
case '%': return 3;
case '^': return 4;
}
return 5;
};
int delprobel(char* string){
int n=dlstr(string);
char* bufer=new char(n+1);
int i=0,j=0,dlst=0;
for(i=0;i<=n;i++) bufer[i]=0;
i=0;
while(string[i]!=0){
if(string[i]!=' '){
bufer[j]=string[i];
i++;
j++;
}else{
i++;
}
};
dlst=j;
j=0;
while(bufer[j]!=0){
string[j]=bufer[j];
j++;
};
for(;j<i;j++)string[j]=0;
delete bufer;
return dlst;
};
char kod(char i){
if( '0'<=i&&i<='9' ) return 'f';//figure
if( 'A'<=i&&i<='Z' ||
'a'<=i&&i<='z' ||
i=='_' ) return 'l';//letter
if( i=='*'||
i=='+'||
i=='-'||
i=='/'||
i=='^'||
i=='%' ) return 'o';//operation
if( i=='(' ) return '(';
if( i==')' ) return ')';
if( i=='.' ) return '.';
if( i=='=' ) return '=';
return 'm';//mistake
};
int dlstr(char* string){
int i=0;
while(string[i]!=0){
i++;
};
return i;
};
int proverka(char* string){
char cLast,current=kod(string[0]);
int iBrackets=0,iLetters=0,i=0;
switch(current){
/*figure*/case 'f': cLast='f';i++;break;
/*letter*/case 'l': cLast='l';i++;break;
/*operation*/case 'o': cout<<"Nel'zja nachinat' s \""<<string[0]<<"\"!\n";return 0;
case '(': cLast='(';iBrackets++;i++;break;
case ')': cout<<"Nel'zja nachinat' s \")\"!\n";return 0;
case '.': cout<<"Nel'zja nachinat' s \".\"!\n";return 0;
case '=': cout<<"Nel'zja nachinat' s \"=\"!\n";return 0;
/*mistake*/case 'm': cout<<"Nel'zja ispol'zovat' \""<<string[0]<<"\"!\n";return 0;
default: cout<<"1BUG!!!\n"; exit(1);
};
while(string[i]!=0){
current=kod(string[i]);
switch(current){
case 'f':
switch(cLast){
case 'f': cLast='f';i++;break;
case 'l': cLast='f';i++;iLetters=2;break;
case 'o': cLast='f';i++;break;
case '(': cLast='f';i++;break;
case ')': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '.': cLast='f';i++;break;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"2BUG!!!\n"; exit(1);
};break;
case 'l':
switch(cLast){
case 'f': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case 'l': cLast='l';i++;break;
case 'o': cLast='l';i++;break;
case '(': cLast='l';i++;break;
case ')': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"3BUG!!!\n"; exit(1);
};break;
case 'o':
iLetters=0;
switch(cLast){
case 'f': cLast='o';i++;break;
case 'l': cLast='o';i++;break;
case 'o': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '(': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case ')': cLast='o';i++;break;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"4BUG!!!\n"; exit(1);
};break;
case '(':
iLetters=0;
switch(cLast){
case 'f': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case 'l': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case 'o': cLast='(';iBrackets++;i++;break;
case '(': cLast='(';iBrackets++;i++;break;
case ')': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"5BUG!!!\n"; exit(1);
};break;
case ')':
iLetters=0;
switch(cLast){
case 'f':
iBrackets--;
if(iBrackets<0){
cout<<"1Narushen balans skobok!\n";return 0;
}else{
cLast=')';i++;
};break;
case 'l':
iBrackets--;
if(iBrackets<0){
cout<<"2Narushen balans skobok!\n";return 0;
}else{
cLast=')';i++;
};break;
case 'o': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '(': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case ')':
iBrackets--;
if(iBrackets<0){
cout<<"3Narushen balans skobok!\n";return 0;
}else{
cLast=')';i++;
};break;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"6BUG!!!\n"; exit(1);
};break;
case '.':
switch(cLast){
case 'f':
if(iLetters==0){
iLetters=1;i++;cLast='.';
}else{
if(iLetters==1){
cout<<"Tochka tol'ko odna!\n";return 0;
}else{
cout<<"Tochka tol'ko v tcifrah!\n";return 0;
};
};break;
case 'l': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case 'o': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '(': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case ')': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko v kontce!\n";return 0;
default: cout<<"7BUG!!!\n"; exit(1);
};break;
case '=':
iLetters=0;
switch(cLast){
case 'f': cLast='=';i++;break;
case 'l': cLast='=';i++;break;
case 'o': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '(': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case ')': cLast='=';i++;break;
case '.': cout<<"Nel'zja \""<<string[i]<<"\" posle \""<<string[i-1]<<"\"!\n";return 0;
case '=': cout<<"Znak \"=\" tol'ko odin!\n";return 0;
default: cout<<"8BUG!!!\n"; exit(1);
};break;
case 'm': cout<<"Nel'zja ispol'zovat' \""<<string[i]<<"\"!\n";return 0;
default: cout<<"9BUG!!!\n"; exit(1);
};
};//end while
if(iBrackets!=0){cout<<"4Narushen balans skobok!\n";return 0;};
if(cLast!='='){cout<<"Net \"=\" v kontce!\n";return 0;};
return 1;
};//end proverka
Ключевые слова:
стек, очередь, польская запись
