用 C语言实现中缀表达式转为后缀表达式 +全代码+解析
#include <>
#include <>
#include<>
#define MaxSize 40
typedef struct
{
char data[MaxSize];
int top;
} Stack,*Stacks;
Stack * init_Stack(Stacks s)//初始化栈
{
s=(Stack*)malloc(sizeof(Stack));
s->top=-1;
printf("初始化成功!\n");
return s;
}
Stack * push(Stacks s,char x)//入栈
{
if(s->top==MaxSize-1)
{
printf("栈满!\n");
}
else
{
s->top=s->top+1;
s->data[s->top]=x;
}
return s;
}
char pop(Stacks s)//出栈
{
char x='0';
if(s->top==-1)
{
printf("使用pop导致栈空!\n");
}
else
{
x=s->data[s->top];
s->top=s->top-1;
}
return x;
}
char get_top(Stacks s)//取栈顶元素
{
char x='0';
if(s->top==-1)
{
printf("栈空!\n");
}
else
{
x=s->data[s->top];
}
return x;
}
int judge(char s)//比较当前扫描到的是数字还是运算符还是括号
{
if(s>='1' && s<='9' ) //49~57
{
return 1;//表示是数字
}
else if(s=='(')
{
return 2;//表示左括号
}
else if(s==')')
{
return 3;//表示右括号
}
else
{
return 4;//表示运算符
}
}
bool compare(char a,char b)//运算符之间优先级比较
{
if((a=='+' || a=='-') &&( b=='+' || b=='-'))//同级和比栈顶低一级，都执行相同的操作:出栈
{
return true;//表示同级
}
else if((a=='+' || a=='-') && (b=='*' || b=='/'))
{
return true;//表示低一级
}
else if((a=='*' || a=='/') && (b=='*' || b=='/'))
{
return true;//表示同级
}
else if((a=='*' || a=='/') && (b=='+' || b=='-'))
{
return false;//表示比栈顶高一级，则入栈
}
}
void display(Stacks s)//显示栈内元素
{
int i=1;
int temp=s->top;//保存指向栈顶的位置，方便复原
while(s->top!=-1)
{
printf("data%d=%c\n",i++,s->data[s->top--]);
}
s->top=temp;
}
void middle_to_postfix(char str1[],int length) //中缀转后缀
{
Stacks s;
s=init_Stack(s);
char str2[length];//用来保存后缀表达式
int j=0;//当作str2的下标
for(int i=0; i<length; i++)
{
if(judge(str1[i]) == 1) //如果是数字，则直接放进str2
{
str2[j++]=str1[i];
}
else//扫描到的不是数字
{
if(s->top==-1 || judge(str1[i])==2 ) //如果栈空，表明之前没有符号，直接将符号入栈;左括号也直接入栈
{
s=push(s,str1[i]);
}
else if(judge(str1[i])==3) //当前扫描到右括号，则出栈，遇到左括号为止
{
while(get_top(s)!='(')
{
str2[j++]=pop(s);
}
pop(s);//最后再把左括号出栈
}
else if(judge(str1[i])==4) //栈不为空，且当前扫描到的是运算符，比较当前运算符与栈顶运算符的运算优先级
{
if(s->data[s->top]=='(') //栈顶是左括号，直接入栈
{
push(s,str1[i]);
}
else if(compare(str1[i],get_top(s)) && s->top!=-1) //是同级，或比栈顶低一级，则出栈，
{
str2[j++]=pop(s);
push(s,str1[i]);//再把当前同级的符号入栈
}
else //比栈顶元素，高一级则入栈
{
s=push(s,str1[i]);
}
}
}
}
while(s->top!=-1)//将栈内剩余的全部输出
{
str2[j++]=s->data[s->top--];
}
for(int i=0; i<j; i++)//显示最后的后缀表达式
{
printf("%c ",str2[i]);
}
}
int main()
{
char a[40]= {0};
gets(a);
int length=0;
while(a[length]!='\0')
{
printf("已输入:%c\n",a[length++]);
}
middle_to_postfix(a,length);
return 0;
}