这是2014年ACM亚洲区预赛牡丹江现场赛的一道题，铜牌题，可惜当时一路WA到死。。。
只有乘法的后缀表达式的特点有两个：（1）数字的数量一定大于‘*’的数量（2）最后一位一定是‘*’；
数字比*多的话，*怎么排列都无所谓，因为1111即可以看成4个1，也可以看成1111，总可以与‘*’
结合。所以在模拟之前做以下预处理：（1）把缺少的数字补上（2）把最后一位1与前面的任何‘*’交换
开始模拟，一个‘*’能被结合，必须前面有大于或者等于2个数字，所以设置一个栈，遇到一个栈，就入
栈一个数字，遇到一个‘*’，如果栈里面1的个数少于2个，则把‘*’与后面的数字交换，等stack里的数字》=2时；
出栈一次，模拟到字符串尾即可；
至于why，只要数字够用即可，所以当遇到‘*’前面的数字不够时，不是插入1，而是将*与后面的1交换。。总之是fuck the dog！。。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <queue> #include <stack> #define INF 0x3f3f3f3f using namespace std; const int maxn = 10005; typedef long long ll; int t; string ss; int len; int main() { //freopen("in","r",stdin); scanf("%d",&t); while(t--) { stack<int> s; queue<int> que; ss = ""; cin>>ss; len = ss.size(); int op = 0; int sch = 0,snum = 0; int pos; for(int i = 0; i < len; ++i) { if(ss[i] == ‘*‘) sch++; else snum++; } if(sch >= snum){ for(int i = 0; i < sch-snum+1; ++i) { ss=‘1‘+ss; } op+=sch-snum+1; } if(sch > 0&&ss[ss.size() - 1] != ‘*‘){ for(int i = 0; i < ss.size(); ++i) if(ss[i] == ‘*‘) { pos = i;break; } swap(ss[pos],ss[ss.size() - 1]); op+=1; } for(int i = ss.size() - 1; i >= 0; --i) { if(ss[i] != ‘*‘) que.push(i); } for(int i = 0; i < ss.size(); ++i) { if(ss[i] == ‘*‘) { if(s.size() == 1){ pos = que.front();//cout<<pos<<endl; swap(ss[i],ss[pos]); que.pop(); op++; s.push(1); } else if(s.size() == 0){ int pos = que.front(); swap(ss[i],ss[pos]); que.pop(); pos = que.front(); swap(ss[i],ss[pos]); que.pop(); op+=2; s.push(1); s.push(1); } else s.pop(); } else{ s.push(1); } } printf("%d\n",op); } }
原文：http://www.cnblogs.com/Norlan/p/4864334.html