中缀表达式转后缀表达式

中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。

pat：表达式转换（25）

 1 #include<stdio.h>
 2 #include<stack>
 3 #include<ctype.h>
 4 using namespace std;
 5 int p[300];
 6 int Priority(char a,char b){//判断优先级 
 7     if(a=='(')return 0;
 8     if(p[a]<p[b])return 0;
 9     if(p[a]>=p[b])return 1;
10 }
11 int main(){
12     char s[30],ans[60],tmp[60];
13     int i;
14     stack<char> st;//栈，用来存运算符 
15     p['+']=p['-']=1;//设置优先级 
16     p['*']=p['/']=2;
17     while(scanf("%s",s)!=EOF){
18         int j=0,k=0;//j：答案的指针；k：标记 
19         for(i=0;s[i];i++){
20             if(s[i]=='(')//左括号直接进栈 
21                 st.push(s[i]);
22             else if(s[i]==')'){//将左括号后边的符号依次输出 
23                 if(k){
24                     ans[j++]=' ';
25                     k=0;
26                 }
27                 while(st.top()!='('){
28                     ans[j++]=st.top();
29                     ans[j++]=' ';
30                     st.pop();
31                 }
32                 st.pop();//删除左括号 
33             }
34             else if(s[i]>='0'&&s[i]<='9'||s[i]=='.'){//数字，包括小数 
35                 ans[j++]=s[i];
36                 k=1;
37             }
38             else{// +-*/ 
39                 if(k){//如果k==1，说明前面有数字，添加一个空格，并重置k 
40                     ans[j++]=' ';
41                     k=0;
42                 }
43                 if((s[i]=='+'||s[i]=='-')&&i==0){//正负号 1
44                     if(s[i]=='-')
45                         ans[j++]=s[i];
46                     continue;
47                 }
48                 if((s[i]=='+'||s[i]=='-')&&i!=0&&s[i-1]=='('){//正负号 2 
49                     if(s[i]=='-')    ans[j++]=s[i];
50                     st.pop();
51                     while(s[++i]!=')'){//这里的右括号要特殊处理 
52                         ans[j++]=s[i];
53                     }
54                     ans[j++]=' ';
55                     continue;
56                 }
57                 while(!st.empty()&&Priority(st.top(),s[i])){//弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈 
58                     ans[j++]=st.top();
59                     ans[j++]=' ';
60                     st.pop();
61                 }
62                 st.push(s[i]);
63             }
64         }
65         if(k){
66             ans[j++]=' ';
67             k=0;
68         }
69         while(!st.empty()){//最后弹出所有运算符 
70             ans[j++]=st.top();
71             ans[j++]=' ';
72             st.pop();
73         }
74         ans[j-1]=0;//将最后一个空格去掉 
75         puts(ans);
76     }
77     return 0;
78 }