这是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 = ;
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 = ;
int sch = ,snum = ;
int pos;
for(int i = ; i < len; ++i)
{
if(ss[i] == '*') sch++;
else snum++;
}
if(sch >= snum){
for(int i = ; i < sch-snum+; ++i)
{
ss=''+ss;
}
op+=sch-snum+;
}
if(sch > &&ss[ss.size() - ] != '*'){
for(int i = ; i < ss.size(); ++i)
if(ss[i] == '*') {
pos = i;break;
}
swap(ss[pos],ss[ss.size() - ]);
op+=;
}
for(int i = ss.size() - ; i >= ; --i)
{
if(ss[i] != '*') que.push(i);
}
for(int i = ; i < ss.size(); ++i)
{
if(ss[i] == '*')
{
if(s.size() == ){
pos = que.front();//cout<<pos<<endl;
swap(ss[i],ss[pos]);
que.pop();
op++;
s.push();
}
else if(s.size() == ){
int pos = que.front();
swap(ss[i],ss[pos]);
que.pop();
pos = que.front();
swap(ss[i],ss[pos]);
que.pop();
op+=;
s.push();
s.push();
}
else s.pop();
}
else{
s.push();
}
}
printf("%d\n",op);
}
}