Перевод из инфиксной записи в обратную польскую — C++(Си)

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
static p=4;
struct st                  // opisanie el-ta steka
{  char c;
    st *next;
};
//-=-=-=-=-=-=-=-=-=-=-=-=-FUNKTION-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-==-==-=-=-=-

st *push(st *,char);       // zanesenie v stek
char pop(st **);            //  chtenie iz steka
int PRIOR(char);          // vozvrashaet PRIORitet operacii

//-=-=-=-=-==-=-=-=-=-=-=-=-=-MAIN-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-==

void main(void)
{
   st *OPR=NULL;           // stek operacii pust
   char in[80],out[80];       // vhodnaya i vihodnie stroki
   int k,point;
   do
   {  puts("vvedite virajenie(v konce simvol '='):");
       fflush(stdin);
       gets(in);                                      // vvod arifmeticheskogo virajeniya
       k=point=0;
       while(in[k]!='\0' && in[k]!='=') // poka ne doidem do ravno '='
      {  if(in[k]==')')                            // esli ocherednoi simvol - ')'
	 { while((OPR->c)!='(')             // to udalyaem iz steka v
	    out[point++]=pop(&OPR);   // vihodnyu stroku vse znaki operacii
							   //  do otkrivaushei skobki
	    pop(&OPR); // udalyaem iz steka otkrivaushyu skobky
	 }
	 if(in[k]>='a' && in[k]<='z')    // esli simvol-bykva, to
	 out[point++]=in[k];                 // zanosim ee v vihodnyu stroky
	 if(in[k]=='(')                            // esli ocherednoi simvol - '(' ,to
	 OPR=push(OPR,'(');                // zanosim ego v stek
	 if(in[k]=='+' || in[k]=='-' || in[k]=='/' || in[k]=='*' || in[k]=='^')
	 {                  //  esli sledyushii simvol - znak operacii ,to vse
			    //  nahodyashiesya v steke operacii s bolshim ili ravnim
			    //  prioritetom perepisyvautsya v vihodnyu stroky
	     while((OPR!=NULL)&&(PRIOR(OPR->c)>=PRIOR(in[k])))
	     out[point++]=pop(&OPR);
	     OPR=push(OPR,in[k]); // zapis v stek novoi operacii
	 }
	 k++;          // perehod k next simvoly vhodnoi stroki
     }
     while(OPR)                         // posle rassmotreniya vsego virajeniya
     out[point++]=pop(&OPR); // perezapis operacii
     out[point]='\0';                    // iz steka v vihodnyu stroky
     printf("\n%s\n",out);           // i pechataem ee
     fflush(stdin);
     puts("\nprodoljit(y/n)?");
 } while(getch()!='n');
}

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=PUSH-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

  // push zapisivaet v stek simvol a, vozvrashyaet
  // ukazatel na novyu vershiny steka
st *push(st *head,char a)
{  st *PTR;
    if(!(PTR=(st*) malloc(sizeof(*PTR))))
   {  puts("no memory"); exit(-1);}
       PTR->c=a;              //
       PTR->next=head;   //
       return PTR;             // PTR -novaya virshina steka
   }

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-POP-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

  // pop   udalyaet simvol s vershini steka. vozvrashaet
  // ydalyaemii simvol. Izmenyaet ukazatel na vershiny steka
char pop(st **head)
{  st *PTR;
    char a;
    if(!(*head)) return '\0';  //esli stek pust, vozvrashyaem \0
    PTR=*head;                 // v PTR - adres vershini steka
    a=PTR->c;
    *head=PTR->next;     // izmenyaem adres vershini steka
    free(PTR);                  // free memory
    return a;                      // vozvrat simvola s vershini steka
}

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-PRIOR-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

  // funk PRIOR vozvrashyaet prioritet arifmeticheskoi operacii
int PRIOR(char a)
{

 switch(a)
   {  case '^':return p++;
     case '*':case '/':return 3;
      case '-':case '+':return 2;
      case '(':return 1;
   } return 0;
}

//-=-=-=-=-=-==-=-=-=-=-==-=-==-=-KONEC:)-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Leave a Comment