直接上代码:
/*中缀表达式 转换成 后缀表达式(逆波兰式)*/
#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;
}