中綴式變後綴式

中綴式變後綴式

中綴式變後綴式

描述

人們的日常習慣是把算術表達式寫成中綴式，但對於機器來說更“習慣於”後綴式，關於算術表達式的中綴式和後綴式的論述一般的數據結構書都有相關內容可供參看，這裡不再贅述，現在你的任務是將中綴式變為後綴式。

輸入

第一行輸入一個整數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 / =

代碼：

#include
int main()
{
	int T,i,top;
	char str[1005],ch[1005];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",str);
		top=-1;
		for(i=0;str[i]!='\0';i++)
		{
			if(str[i]>='0'&&str[i]<='9')
			{
				while((str[i]=='.')||(str[i]>='0'&&str[i]<='9'))
				{
					printf("%c",str[i]);
					i++;
				}
				printf(" ");
			}
			if(str[i]=='=')
				break;
			if(str[i]==')')
			{
				while(top>=0&&(ch[top]!='('))
				{
					printf("%c ",ch[top]);
					top--;
				}
				top--;
			}
			else if(str[i]=='(')
			{
				top++;
				ch[top]=str[i];
			}
			else if(str[i]=='*'||str[i]=='/')
			{
				while((ch[top]=='*')||(ch[top]=='/'))
				{
					printf("%c ",ch[top]);
					top--;
				}
				top++;
				ch[top]=str[i];
			}
			else
			{
				while(top>=0&&(ch[top]!='('))
				{
					printf("%c ",ch[top]);
					top--;
				}
				top++;
				ch[top]=str[i];
			}
		}
		while(top>=0)
		{
			printf("%c ",ch[top]);
			top--;
		}
		printf("=\n");
	}
	return 0;
}