首页 > 代码库 > 中缀式变后缀式
中缀式变后缀式
中缀式变后缀式
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
人们的日常习惯是把算术表达式写成中缀式，但对于机器来说更“习惯于”后缀式，关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看，这里不再赘述，现在你的任务是将中缀式变为后缀式。
输入
第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式的中缀式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0
输出
每组都输出该组中缀式相应的后缀式，要求相邻的操作数操作符用空格隔开。
样例输入
2
1.000+2/4=
((1+2)*5+1)/4=
样例输出
1.000 2 4 / + =
1 2 + 5 * 1 + 4 / =
题解：主要完成对数组postexp中指定位置添加空格。
程序代码：
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 1000
#define MaxOp 7
struct //设定运算符优先级
{
char ch; //运算符
int pri; //优先级
} lpri[]={{‘=‘,0},{‘(‘,1},{‘*‘,5},{‘/‘,5},{‘+‘,3},{‘-‘,3},{‘)‘,6}},
rpri[]={{‘=‘,0},{‘(‘,6},{‘*‘,4},{‘/‘,4},{‘+‘,2},{‘-‘,2},{‘)‘,1}};
int leftpri(char op) //求左运算符op的优先级
{
int i;
for (i=0;i<MaxOp;i++)
if (lpri[i].ch==op)
return lpri[i].pri;
}
int rightpri(char op) //求右运算符op的优先级
{
int i;
for (i=0;i<MaxOp;i++)
if (rpri[i].ch==op)
return rpri[i].pri;
}
int InOp(char ch) //判断ch是否为运算符
{
if (ch==‘(‘ || ch==‘)‘ || ch==‘+‘ || ch==‘-‘ || ch==‘*‘ || ch==‘/‘)
return 1;
else
return 0;
}
int Precede(char op1,char op2) //op1和op2运算符优先级的比较结果
{
if (leftpri(op1)==rightpri(op2))
return 0;
else if (leftpri(op1)<rightpri(op2))
return -1;
else
return 1;
}
void trans(char *exp,char postexp[])
//将算术表达式exp转换成后缀表达式postexp
{
struct
{
char data[MaxSize]; //存放运算符
int top; //栈指针
} op; //定义运算符栈
int i=0; //i作为postexp的下标
op.top=-1;
op.top++; //将‘=‘进栈
op.data[op.top]=‘=‘;
while (*exp!=‘\0‘) //exp表达式未扫描完时循环
{
if(*exp==‘=‘)
break;
if (!InOp(*exp)) //为数字字符的情况
{
while (*exp>=‘0‘ && *exp<=‘9‘ || *exp==‘.‘) //判定为数字
{
postexp[i++]=*exp;
exp++;
}
// postexp[i++]=‘#‘; //用#标识一个数值串结束
postexp[i++]=‘ ‘;
}
else //为运算符的情况
switch(Precede(op.data[op.top],*exp))
{
case -1: //栈顶运算符的优先级低:进栈
op.top++;
op.data[op.top]=*exp;
exp++; //继续扫描其他字符
break;
case 0: //只有括号满足这种情况
op.top--; //将(退栈
exp++; //继续扫描其他字符
break;
case 1: //退栈并输出到postexp中
postexp[i++]=op.data[op.top];
postexp[i++]=‘ ‘;
op.top--;
break;
}
} //while (*exp!=‘\0‘)
while (op.data[op.top]!=‘=‘)
//此时exp扫描完毕,退栈到‘=‘为止
{
postexp[i++]=op.data[op.top];
postexp[i++]=‘ ‘;
op.top--;
}
postexp[i++]=‘=‘; //给postexp表达式添加结束标识
postexp[i++]=‘\0‘;
}
int main()
{
int n;
scanf("%d",&n);
getchar();
while(n--)
{
char exp[MaxSize];
scanf("%s",exp);
char postexp[MaxSize];
trans(exp,postexp);
printf("%s\n",postexp);
}
system("pause");
return 0;
}