下面是我做这题的思想以及具体程序,不知道大家觉得这样做好不好,我是用递归做的.
/*思想:
1.第一个字符肯定先放到新数组.
2.假如碰到'*',或者'/'的话就先把这个符号后面的那个字符放入新数组,然后再将符号压进去.
3.假如碰到'+','-'的话,假如下一个符号的优先级和它们一样就用同上的方法,假如后面符号的优先级比它们
高的话就用for循环来查找下一个与它们优先级一样的符号.假如查到的话在完成后面的符号全都放入新数组后就把这个符号放入新数组,然后再执行后面的递归.假如前面没查到相同优先级符号的话就把后面的符号都放入新数组后再把这个符号放进去.做这一步中因为牵涉到后面'*','/'符号都放入后要回到原来的位置,所以就用了个yes变量来判定是否碰到这种要返回的情况,假如yes=1,就表示有这种情况,有些地方需要非凡判定.
4.假如要再加入括号的话我觉得可以再用一个类似yes类型的变量就可以完成.
*/
#define N 80
int i=0,yes=0;/*i是新数组的下标指示,yes变量用来判定'+','-'后面假如有'*','/'的情况*/
void Input(char *x);/*输入表达式*/
void Output(char *x);/*输出逆波兰*/
int Fun(char *x,char *y,int n);/*递归函数*/
void main(void)
{
char x[N],y[N];
Input(x);
Fun(x,y,1);
Output(y);
}
int Fun(char *x,char *y,int n)/*递归函数*/
{int j;
if(x[n]==' ')/*递归到了结束运算符*/
{
y[n]=' ';
return;
}
if(n==1)/*第一次递归把第一个元素放入新数组*/
y[i++]=x[0];
if(x[n]=='*'||x[n]=='/')/*乘除号的判定*/
{
y[i++]=x[n+1];
y[i++]=x[n];
if(yes&&(x[n+2]=='+'||x[n+2]=='-'))/*这里两句if是用来判定yes存在的情况下的*/
{yes=0;return;}
if(yes&&x[n+2]==' ')
return;
Fun(x,y,n+2);
}
else if(x[n]=='+'||x[n]=='-')/*加减号的判定*/
{
if(x[n+2]!='*'&&x[n+2]!='/')/*直接放入新表达式的情况*/
{
y[i++]=x[n+1];
y[i++]=x[n];
Fun(x,y,n+2);
}
else/*后面有乘除号的情况*/
{
yes=1;
y[i++]=x[n+1];
for(j=n+2;;j+=2)
{
if(x[j]==' '||x[j]=='+'||x[j]=='-')
break;
}
if(x[j]==' ')/*后面的乘除直接到表达式结束的情况*/
{
Fun(x,y,n+2);
y[i++]=x[n];
y[i]=' ';
yes=0;
}
else/*后面还有加减号的情况*/
{
Fun(x,y,n+2);
y[i++]=x[n];
yes=0;
Fun(x,y,j);
}
}
}
}
void Input(char *x)/*输入中缀表达式*/
{
clrscr();
printf("please input: ");
gets(x);
}
void Output(char *x)/*输出转换后的后缀表达式*/
{
printf("Now: ");
puts(x);
getch();
}