#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1000
using namespace std;
char s[N];//存储字符串
char str1[N];//存储‘o‘-到‘9‘的字符
char str2[N];//存储运算符
int top1,top2;//利用数组模拟栈
int compare(char x)//优先级比较
{
switch(x)
{
case ‘+‘ :
case ‘-‘ :return 1;
case ‘*‘ :
case ‘/‘ :return 2;
case ‘(‘ :return 0;
default: return -1;
}
}
void zhuan()//转换
{
int k;
top1=-1,top2=-1;//初始化头
scanf("%s",s);
k=strlen(s);
for(int i=0;i<k;i++)
{
if(s[i]>=‘0‘&&s[i]<=‘9‘||s[i]==‘.‘)
{
top1++;
str1[top1]=s[i];
}
else if(s[i]==‘(‘)
{
top2++;
str2[top2]=s[i];
}
else if(s[i]==‘)‘)
{
while(str2[top2]!=‘(‘)
{
top1++;
str1[top1]=‘ ‘;
top1++;
str1[top1]=str2[top2];
top2--;
}
top2--;;
}
else if(s[i]==‘+‘||s[i]==‘-‘||s[i]==‘*‘||s[i]==‘/‘)
{
top1++;
str1[top1]=‘ ‘;
while(compare(s[i])<=compare(str2[top2]))
{
top1++;
str1[top1]=str2[top2];
top1++;
str1[top1]=‘ ‘;
top2--;
}
top2++;
str2[top2]=s[i];
}
}
while(top2!=-1)
{
top1++;
str1[top1]=‘ ‘;
top1++;
str1[top1]=str2[top2];
top2--;
}
top1++;
str1[top1]=‘ ‘;
top1++;
str1[top1]=‘=‘;
top1++;
str1[top1]=‘\0‘;
for(int i=0;i<top1;i++)
printf("%c",str1[i]);
printf("\n");
}
main()
{
int n;
scanf("%d",&n);
while(n--)
{
zhuan();
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
南阳 oj 中缀式变后缀式 题目467 数据结构 NYOj
原文：http://blog.csdn.net/yueloveme/article/details/47058155
