（SPOJ4）Transform the Expression

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

ExampleInput:

3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

算法描述：
栈底放‘#’，从左至右逐字读取中缀式：
1.当前字符为数字时，直接输出；
2.当前字符为"("时，将其压栈；
3.当前字符为")"时，则弹出堆栈中最上的"("之前的所有运算符并输出，然后删除堆栈中的"(" ；
4.当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到"("之前为止)，输出，再将当前运算符压栈；

AC code：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <ctype.h>
 5 
 6 char a[410],stack[400];
 7 
 8 void deal(char *s)
 9 {
10     int i,j,L=strlen(s);
11     stack[0]='#';
12     j=1;
13     for(i=0; i<L; i++)
14     {
15         if(isalpha(s[i]))
16         {
17           printf("%c",s[i]);
18         }
19         else if(s[i]=='(')
20         {
21           stack[j++]='(';
22         }
23         else
24         {
25           switch(s[i])
26             {
27             case '+':
28             case '-':
29              while(stack[j-1]!='(' && j>0)
30              {
31                printf("%c",stack[j-1]);
32                stack[j-1]=' ';
33                j--;      
34              }
35              stack[j++]=s[i];
36              break;
37              case '*':
38              case '/':
39              while(stack[j-1]!='(' && (stack[j-1]=='*' || stack[j-1]=='/' || stack[j-1]=='^') && j>0)
40              {
41                  printf("%c",stack[j-1]);
42                  stack[j-1]=' ';
43                  j--;
44              }
45              stack[j++]=s[i];
46              break;
47              case '^': stack[j++]=s[i]; break;
48              case ')':
49              while(stack[j-1]!='(' && j>0)
50              {
51                  printf("%c",stack[j-1]);
52                  stack[j-1]=' ';
53                  j--;
54              }
55              j--;
56              break;
57              default:break;
58           }
59         }
60     }
61     printf("\n");
62 }
63 void solve()
64 {
65     int t,n;
66     scanf("%d",&t);
67     getchar();
68     while(t--)
69     {
70         gets(a);
71         deal(a);
72     }
73 }
74 
75 int main()
76 {
77   solve();
78   return 0;
79 }