将中缀表达式转化成后缀表达式（逆波兰式）

直接上代码：

 

/*中缀表达式 转换成 后缀表达式（逆波兰式）*/#include<stdio.h>#include<stdlib.h>

struct Stack{ int Capacity; int top; char *Array;};

int get_priority(char c){ if( (c=='+')  ||  (c =='-') )  return 1; else if( (c=='*')  ||  (c =='/') )  return 2; else  return 0;}

int IsEmpty(struct Stack S){ return S.top==-1;}

struct Stack*  CreateStack(unsigned int len){ struct Stack *S=(struct Stack *)malloc(sizeof(struct Stack));

 S->Capacity=len; S->top=-1; S->Array=(char *) malloc(len *sizeof(char) ); return S;}

void push(struct Stack *S,char value){ S->top++; if(S->top >= S->Capacity) {  printf("Stack is full/n");  exit(-1); } S->Array[S->top]=value;}

void  pop(struct Stack *S){  if(S->top==-1) {  printf("Stack is empty/n");  exit(-1); }  S->top--;}

char get_top(struct Stack S){ if(S.top==-1)  return ' '; else  return S.Array[S.top];}

Transcode(char string1[],char string2[],int len){ char value; char value2; int i,j; struct Stack *S; S=CreateStack(100);

 for(i=0,j=0;i<len;i++) {  value=string1[i];  if(  value!='+' &&  value!='-'  && value !='*'  && value!='/'  && value!= '(' && value!=')' )  //如果是数字  {   string2[j++]=value;  }

  else if( value==')')  //右括号  {   char temp;   while( (temp=get_top(*S)) !='(' )   {    string2[j++]=temp;    pop(S);   }   pop(S);  }  else if(value=='(')   {   push(S,value);  }

  else  {   value2=get_top(*S);   if( get_priority(value2) <get_priority(value) )   {    push(S,value);   }   else   {    while(get_priority(value2) >= get_priority(value) )    {     string2[j++]=value2;     pop(S);     value2=get_top(*S);    }    push(S,value);   }  } }

 while(! IsEmpty(*S)) {  value2=get_top(*S);  string2[j++]=value2;  pop(S); } string2[j]='/0';}

int main(){

 char string1[]="a *( (b+c)/d+7)"; char string2[100]; Transcode(string1,string2,sizeof(string1)-1); printf("%s/n",string2); return 0;}