pipioj 1292 中缀表达式转后缀表达式II

 1 #define bug(x) cout<<#x<<" is "<<x<<endl
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int N=2e6+10;
 5 
 6 stack<char>s;
 7 queue<char>q;
 8   
 9 int n;
10 char t[N];
11 
12 void solve(){
13     for(int i=1;i<=n;i++){
14         if(t[i]>='a'&&t[i]<='z')q.push(t[i]);
15         else if(t[i]=='('){
16             s.push(t[i]);
17         }
18         else if(t[i]=='^'){
19             while(!s.empty()&&s.top()=='^'){
20                 q.push(s.top());
21                 s.pop();
22             }
23             s.push(t[i]);
24         }
25         else if(t[i]=='*'||t[i]=='/'){
26             while(!s.empty()&&(s.top()=='^'||s.top()=='*'||s.top()=='/')){
27                 q.push(s.top());
28                 s.pop();
29             }
30             s.push(t[i]);
31         }
32         else if(t[i]=='+'||t[i]=='-'){
33             while(!s.empty()&&s.top()!='('){
34                 q.push(s.top());
35                 s.pop();
36             }
37             s.push(t[i]);
38         }
39         else{
40             while(!s.empty()&&s.top()!='('){
41                 q.push(s.top());
42                 s.pop();
43             }
44             s.pop();
45         }
46     }
47     while(!s.empty()){
48         q.push(s.top());
49         s.pop();
50     }
51     while(!q.empty()){
52         printf("%c",q.front());
53         q.pop();
54     }
55 }
56 int main(){
57     scanf("%s",t+1);
58     n=strlen(t+1);
59     solve();
60 }