CCF算法笔记2 二十四点

二十四点"/>

CCF算法笔记2 二十四点

分析：题目很容易理解，我们只需要模拟四则运算即可，题目设限简单，我们只需要进行四个个位数的加减乘除运算即可，并且还不包括括号。当结果等于24时，即可输出结果“Yes”，否则输出“No”。
这道题的解题方法有很多，

1. 首先最简单的暴力法，因为只设计到四个个个位数加减，我们只需要把所有情况都列出来即可，一共4^3=64种，这种方法空间占用比较少，因为没有涉及到STL，但是时间比较多，因为需要逐个判断。
2. 经典的四则运算用到的栈的方法，生成两个栈，分别保存数字和符号，当遇到+、-时符号直接入栈，当遇到*、/时，先计算符号前后两个数再入栈，最后遍历数字栈，插入+、-号，通过数字出栈入栈，栈得到的最后一个数即最终结果。
   代码，穷举法的：

#include <iostream>   //头文件不需要这么多，习惯粘上所有的
#include <cstdio>
#include <set>   //自动排序， 不可重复  unordered_set
#include <sstream>    
#include <string>  //char[] , string 
#include <typeinfo>
#include <algorithm>  //sort()   cmp
#include <vector>
#include <map>   //map a;   a.insert(pair<,>,())   a[10]="qewe"; 
#include <cctype> 
#include <iomanip>   //cout<<setw(10)<<left
#include <queue>
#include <cmath>//printf("%.2f",a)
using namespace std;int main()
{int n;cin>>n;while(n--){int r=0;int a=0,b=0,c=0,d=0;string s;cin>>s;a=s[0]-'0';b=s[2]-'0';c=s[4]-'0';d=s[6]-'0';//暴力循环if(s[1]=='+'){	if(s[3]=='+'){if(s[5]=='+') r=a+b+c+d;else if(s[5]=='-') r=a+b+c-d;else if(s[5]=='/') r=a+b+c/d;else r=a+b+c*d;}else if(s[3]=='-') {if(s[5]=='+') r=a+b-c+d;else if(s[5]=='-') r=a+b-c-d;else if(s[5]=='/')r=a+b-c/d;else r=a+b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a+b/c+d;else if(s[5]=='-') r=a+b/c-d;else if(s[5]=='/') r=a+b/c/d;else r=a+b/c*d;}else {if(s[5]=='+') r=a+b*c+d;else if(s[5]=='-') r=a+b*c-d;else if(s[5]=='/')r=a+b*c/d;else r=a+b*c*d;}}else if(s[1]=='-') {	if(s[3]=='+'){if(s[5]=='+') r=a-b+c+d;else if(s[5]=='-') r=a-b+c-d;else if(s[5]=='/')r=a-b+c/d;else r=a-b+c*d;}else if(s[3]=='-') {if(s[5]=='+') r=a-b-c+d;else if(s[5]=='-') r=a-b-c-d;else if(s[5]=='/')r=a-b-c/d;else r=a-b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a-b/c+d;else if(s[5]=='-') r=a-b/c-d;else if(s[5]=='/') r=a-b/c/d;else r=a-b/c*d;}else {if(s[5]=='+') r=a-b*c+d;else if(s[5]=='-') r=a-b*c-d;else if(s[5]=='/')r=a-b*c/d;else r=a-b*c*d;}}else if(s[1]=='/'){	if(s[3]=='+'){if(s[5]=='+') r=a/b+c+d;else if(s[5]=='-') r=a/b+c-d;else if(s[5]=='/')r=a/b+c/d;else r=a/b+c*d;}else if(s[3]=='-') {if(s[5]=='+')r=a/b-c+d;else if(s[5]=='-') r=a/b-c-d;else if(s[5]=='/')r=a/b-c/d;else r=a/b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a/b/c+d;else if(s[5]=='-') r=a/b/c-d;else if(s[5]=='/')r=a/b/c/d;else r=a/b/c*d;}else {if(s[5]=='+') r=a/b*c+d;else if(s[5]=='-') r=a/b*c-d;else if(s[5]=='/') r=a/b*c/d;else r=a/b*c*d;}}else {	if(s[3]=='+'){if(s[5]=='+') r=a*b+c+d;else if(s[5]=='-') r=a*b+c-d;else if(s[5]=='/')r=a*b+c/d;else r=a*b+c*d;}else if(s[3]=='-') {if(s[5]=='+')r=a*b-c+d;else if(s[5]=='-') r=a*b-c-d;else if(s[5]=='/')r=a*b-c/d;else r=a*b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a*b/c+d;else if(s[5]=='-') r=a*b/c-d;else if(s[5]=='/')r=a*b/c/d;else r=a*b/c*d;}else {if(s[5]=='+') r=a*b*c+d;else if(s[5]=='-')  r=a*b*c-d;else if(s[5]=='/') r=a*b*c/d;else  r=a*b*c*d;}}//	cout<<r<<endl;if(r==24) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
} 

栈的方法，这个是我自己写的，测试没有问题，但是有部分测试点无法通过，有大神知道问题可以给我说一下，，

#include <iostream>  
#include <cstdio>
#include <set>   //自动排序， 不可重复  unordered_set
#include <sstream>    
#include <string>  //擦汗ar[] , string 
#include <typeinfo>
#include <algorithm>  //sort()   cmp
#include <vector>
#include <map>   //map a;   a.insert(pair<,>,())   a[10]="qewe"; 
#include <cctype> 
#include <iomanip>   //cout<<setw(10)<<left
#include <queue>
#include <cmath>//printf("%.2f",a)
#include <stack>
using namespace std;int main()
{int n;cin>>n;while(n--){int r=0;string s;cin>>s;stack<int> shu;stack<char> fu;    //×//利用栈的思想，构造两个栈，遇到乘除优先计算后再入栈，加减直接入栈for(int i=0;i<7;i++){if(s[i]>='0' &&s[i]<='9')//数字入栈 shu.push(s[i]-'0');else {if(s[i]=='+' ||s[i]=='-'){fu.push(s[i]);}else if(s[i]=='/'){//int n;n=shu.top()/(s[i+1]-'0');shu.pop();shu.push(n);//	cout<<"n="<<n<<endl;i++; }else {int n;n=shu.top()*(s[i+1]-'0');shu.pop();shu.push(n);//	cout<<"n="<<n<<endl;i++; }}}while(shu.size()-1) {//当数字栈中至少存在两个元素时，进行加减 int a=shu.top();shu.pop();int b=shu.top();shu.pop();if(fu.top()=='+'){int c=a+b;shu.push(c);//	cout<<"c+="<<c<<endl;}else if(fu.top()=='-'){int c=b-a;shu.push(c);//	cout<<"c-="<<c<<endl;}else break;}r=shu.top();if(r==24) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
} 

下面推荐别人写的栈的方法，参见链接：添加链接描述

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
using namespace std;int n;
char a[10];stack<int> num;
stack<char> sign;
int all;
int main()
{cin>>n;getchar();for(int i=1;i<=n;i++){gets(a);all=0;while(!num.empty())num.pop();while(!sign.empty())sign.pop();int j=0;while(j<strlen(a)){if(a[j]<='9'&&a[j]>='0'){num.push(a[j]-'0');}elseif(a[j]=='+'){sign.push(a[j]);}elseif(a[j]=='-'){sign.push('+');num.push((a[j+1]-'0')*(-1));j++;}elseif(a[j]=='x'){int ans=num.top();num.pop();num.push(ans*(a[j+1]-'0'));j++;}else{int ans=num.top();num.pop();num.push(ans/(a[j+1]-'0'));j++;}j++;}while(!num.empty()){all+=num.top();num.pop();}if(all==24) printf("Yes\n");else printf("No\n");
}return 0;
}