一本通刷题
一本通
栈part
1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1331
it's a very strange prob.I dont know why i cant pass the test in this website while i can pass in sycoj.so i hold the view that its ybt's fault.there's no bugs in my cpp.
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
string s;
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
getline(cin,s);
int len=s.size();
stack q;
rep(i,0,len)
{
if(s[i]>='0'&&s[i]<='9')
{
ll tmp=0;
while(s[i]>='0'&&s[i]<='9') tmp=tmp*10+s[i]-'0',i++;
q.push(tmp);
}
else if(s[i]==' ')continue;
else if(s[i]=='@') break;
else
{
int a,b;b=q.top(),q.pop(),a=q.top(),q.pop();
if(s[i]=='+') q.push(a+b);
if(s[i]=='-') q.push(a-b);
if(s[i]=='*') q.push(a*b);
if(s[i]=='/') q.push(a/b);
}
}
printf("%lld\n",q.top());
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1353
a very easy prob.we have the conception that if the match exists,every right bracket has the corresponding left bracket before. so just count the number of left and right bracket dynamicly.if the cnt>=0 for all the time and it finally turns into zero,we got "yes" otherwise "NO";
http://ybt.ssoier.cn:8088/problem_show.php?pid=1354
为了方便还是中文吧，很离谱，本地和oj不一样，会出现的问题，一种是没有初始化，一种就是输入的数据和实际的数据不一样，比如行末空格。
另外一个方面就是，思路要清晰，不然很容易出现漏解的情况，成立和非成立要划分清楚，比如本题，成立的话不仅要能匹配成功，还要一个不剩。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
string s="";
getline(cin,s);
int len=s.size();
bool flag=true;
stack q;
rep(i,0,len-1)//行末空格问题
{
if(s[i]=='(') q.push(s[i]);
else if(s[i]=='[')q.push(s[i]);
else if((s[i]==')'||s[i]==']')&&!q.size()) {flag=false;break;}
else if(s[i]==')'&&q.top()=='(') {q.pop();}
else if(s[i]==']'&&q.top()=='[') {q.pop();}
// else {flag=false;break;}//可以直接删掉，因为如果不匹配，要么是(多，要么是)多，(会出现非空的情况，)则直接返回false
}
if(flag&&!q.size()) puts("OK");
else puts("Wrong");
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1355
行末空格永远的痛，getline不能随便用，会读入所有的东西，最好还是按照cin来读吧，除非是间断的。另外大小的判断通过数字来比较，此外对于情况，如果好的情况容易列举，那么就好的，如果坏的情况容易列举，那就坏的。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
char a[]={'{','[','(','<','}',']',')','>'};
map p;
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int n;n=read();
rep(i,0,8) p[a[i]]=i;
while(n--)
{
string s;
cin>>s;
int len=s.size();
stack q;
bool flag=true;
rep(i,0,len)
{
if(s[i]=='('||s[i]=='{'||s[i]=='['||s[i]=='<') //getline有风险，慎用。
{
if(!q.size()) q.push(p[s[i]]);
else
{
if(q.top()>p[s[i]]) {flag=false;break;}
q.push(p[s[i]]);
}
}
else if(!q.size()){flag=false;break;}//防止出现问题，没有是无法top的
else if(s[i]==')'&&q.top()==2||(s[i]==']'&&q.top()==1)||(s[i]=='>'&&q.top()==3)||(s[i]=='}'&&q.top()==0)) {q.pop();}
// else q.pop();//匹配成功出去
}
if(flag&&!q.size()) puts("YES");//匹配成功而且还要一个不剩
else puts("NO");
}
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1357
火车进出站，首先是前置条件，如果他要出栈，那么在他前面的一定要么出栈了，要么还在栈里，而出栈本身由其出栈实现了，而在栈只需要模拟即可。
此外先把前置条件实现，然后看在当前的情况下能否出栈，如果有比他更大的数在栈里，那么将无法出栈，那么就无法实现。
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int n;
n=read();
int cur=1;
stack q;
rep(i,1,n+1)//如果要出栈，那么首先前面比他小的数字一定要都要么在栈，要么已经出栈，而已经出栈，这可以由出栈过程本身来实现
{//这是条件，然后在这个条件下模拟进出栈，然后看能不能实现
int x;x=read();
while(cur<=x) q.push(cur++);
if(q.top()==x) q.pop();//模拟过程，如果比他大的数还在栈里面，那么是不可能出栈的。
else {puts("NO");return 0;}//出不了，那就fail
}
puts("YES");
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1356
虽然是一道很烦的题目，但是个人认为是一个不错的题目，很考验你对问题的实现。
首先是如何模拟中缀表达式。
1确定优先级 2防止意外情况
那么基于此，首先先把数字读入，然后遇到括号特殊处理，然后如果是开头，不算因为没有符号，如果是括号不算，因为优先级不高。正常的情况是数字+符号+数字+符号，只要此时的符号大于前面的符号，那么就可以计算
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6;
int n,m;
char st[N];
stack s1;
stack s2;
int level(char x)
{
if(x=='+'||x=='-') return 1;
else if(x=='*'||x=='/') return 2;
else if(x=='^') return 3;
return 0;
}
void cal(stack &s1,stack &s2)
{
int y=s1.top();s1.pop();
int x=s1.top();s1.pop();
char z=s2.top();s2.pop();
if(z=='+')s1.push(x+y);
if(z=='-') s1.push(x-y);
if(z=='*') s1.push(x*y);
if(z=='/' )s1.push(x/y);
if(z=='^') s1.push(int(pow(x,y)));
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
scanf("%s",st+1);
int n=strlen(st+1);
int cnt=0;
bool flag=true;
rep(i,1,n+1)
{
if(st[i]=='(') cnt++;
else if(st[i]==')')
{
cnt--;
if(cnt<0) {flag=false;break;}
}
}
rep(i,2,n+1) if(level(st[i])&&level(st[i-1])) {flag=false;break;}
if(n==1&&level(st[1])||!flag){puts("NO");return 0;}
int tmp=0;
flag=false;
rep(i,1,n+1)
{
if(st[i]>='0'&&st[i]<='9')
{
tmp=(tmp<<3)+(tmp<<1)+st[i]-'0';
flag=true;
}
else
{
if(flag) s1.push(tmp),tmp=0,flag=false;//如果上一个是数字，那么就存下。
if(st[i]=='('){s2.push(st[i]);continue;}//如果不是数字，是括号，那么处理括号
if(st[i]==')')
{
while(s2.top()!='(') cal(s1,s2);
s2.pop();continue;
}
while(!s2.empty()&&level(s2.top())>=level(st[i]))//如果上一个不是括号，且可以运算
{
cal(s1,s2);
}//不是括号，不是数字，只能是符号
s2.push(st[i]); //存入符号
}
}//只有当栈顶元素的优先级大于等于我当前的符号的优先级，我才可以对目前的两个元素进行计算
//同时符号具有最优先，所以要最优处理
//中缀表达式是算前的1+1
//括号用0，是为了防止只有一个数字，在括号里就直接开始算了//开头没有符号，括号优先级不大
if(flag) s1.push(tmp),tmp=0,flag=false;
while(!s2.empty())cal(s1,s2);
printf("%d\n",s1.top());
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1358
和上一题一样是中缀表达式
实际上就是模拟思路
点击查看代码
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answer\n", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
// ok++; //AC数量+1
// }
// }
// printf("\n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6;
int n,m;
char st[N];
stack s1;
stack s2;
int level(char x)
{
if(x=='+'||x=='-') return 1;
else if(x=='*'||x=='/') return 2;
else if(x=='^') return 3;
return 0;
}
void cal(stack &s1,stack &s2)
{
int y=s1.top();s1.pop();
int x=s1.top();s1.pop();
char z=s2.top();s2.pop();
if(z=='+')s1.push(x+y);
if(z=='-') s1.push(x-y);
if(z=='*') s1.push(x*y);
if(z=='/' )s1.push(x/y);
if(z=='^') s1.push(int(pow(x,y)));
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
scanf("%s",st+1);
int n=strlen(st+1);
int cnt=0;
bool flag=true;
rep(i,1,n)
{
if(st[i]=='(') cnt++;
else if(st[i]==')')
{
cnt--;
if(cnt<0) {flag=false;break;}
}
}
rep(i,2,n) if(level(st[i])&&level(st[i-1])) {flag=false;break;}
if(n==1&&level(st[1])||!flag){puts("NO");return 0;}
int tmp=0;
flag=false;
rep(i,1,n)
{
if(st[i]>='0'&&st[i]<='9')
{
tmp=(tmp<<3)+(tmp<<1)+st[i]-'0';
flag=true;
}
else
{
if(flag) s1.push(tmp),tmp=0,flag=false;//如果上一个是数字，那么就存下。
if(st[i]=='('){s2.push(st[i]);continue;}//如果不是数字，是括号，那么处理括号
if(st[i]==')')
{
while(s2.top()!='(') cal(s1,s2);
s2.pop();continue;
}
while(!s2.empty()&&level(s2.top())>=level(st[i]))//如果上一个不是括号，且可以运算
{
cal(s1,s2);
}//不是括号，不是数字，只能是符号
s2.push(st[i]); //存入符号
}
}//只有当栈顶元素的优先级大于等于我当前的符号的优先级，我才可以对目前的两个元素进行计算
//同时符号具有最优先，所以要最优处理
//中缀表达式是算前的1+1
//括号用0，是为了防止只有一个数字，在括号里就直接开始算了//开头没有符号，括号优先级不大
if(flag) s1.push(tmp),tmp=0,flag=false;
while(!s2.empty())cal(s1,s2);
printf("%d\n",s1.top());
end=clock();
// printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}