记录算法小白的辛酸历程
题目描述
题目分析
这个题目的意思就是使用 3 个加减乘除运算使得 4个数字的运算结果为 24。
输入：第1行输入一个整数 n，从第 2 行开始到第 n + 1 行中，每一行包含一个长度为 7的字符串。
输出：包含 n 行，对于每一个游戏，如果其结果为 24 则输出字符串 Yes，否则输出字符串 No。
测试数据：所有测试数据中n都是100（第一个测试点都是正确的，不会做的时候，可以令所有的输出都是YES，通过第一个测试点也可以得10分的！）
错误示例
10分
暴力输出….通过测试点1只有10分
#include <iostream>
using namespace std;
int main() {
char a[100][7];
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < 100; i++)
cout << "Yes" << endl;
}
50分
int main(){
int n;
string s;
cin>>n;
queue<int> num;
queue<char> op;
while(n--){
cin>>s;
s.push_back('+');//add"+" at the end of equatation
for(int i=1;i<s.size();i+=2){
int t=s[i-1]-'0';
for(;i<s.size()&&s[i]=='x'||s[i]=='/';i+=2){
t=(s[i]=='x')?t*s[i+1]-'0':t/s[i+1]-'0';
}
num.push(t);
op.push(s[i]);
}
num.push(0);
int t=num.front();
num.pop();
while(!op.empty()){
char c=op.front();
op.pop();
t=(c=='+')?t+num.front():t-num.front();
num.pop();
}
puts(t==24?"Yes":"No");
}
return 0;
}
先相乘（相除）再转化为int型出错
t=(s[i]=='x')?t*s[i+1]-'0':t/s[i+1]-'0';//-'0'相当于减去0的ASCII码48，将字符型数据转化为int型
优秀实例
数组+栈
先将表达式存储在数组a中（注意要给a申请足够的内存空间），然后再通过遍历a得到运算符和操作数（因为已知每个运算符和操作数在数组中的位置）。将数字压入栈中，遇到x或\则数字出栈与下一个数字运算，遇到-将下一个数字的负数压入栈中，遍历完成后，将栈中的数字全部相加得到表达式的值。
#include <iostream>
#include<stack>
using namespace std;
int main()
{
char a[100][8];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int num[4]; //运算数
char oper[3]; //运算符
int sum = 0;
for (int j = 0; j < 7; j++) {
if (j % 2 == 0)
num[j / 2] = a[i][j] - 48; //0的ASSIC码为48
else
oper[j / 2] = a[i][j];
}
stack<int>snum;
stack<char>soper;
snum.push(num[0]);
for (int i = 0; i < 3; i++)
{
if (oper[i] == 'x' ||oper[i] == '/') {
int temp = snum.top();
snum.pop();
if (oper[i] == 'x')
snum.push(temp*num[i + 1]);
else
snum.push(temp / num[i + 1]);
}
else if (oper[i] == '-') {
snum.push(-num[i + 1]);
soper.push(oper[i]);
}
else {
snum.push(num[i + 1]);
soper.push(oper[i]);
}
}
sum = snum.top();
snum.pop();
for (int i = 0; i < soper.size(); i++) {
sum += snum.top();
snum.pop();
}
if (sum == 24)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
栈+队列
利用堆栈，可设置操作符优先级，将中缀表达式转为后缀表达式，然后计算后缀表达式。
#include<bits/stdc++.h>
using namespace std;
struct node{
int num;//操作数
char op;//操作符
bool flag;//true表示操作数，false表示操作符
};
string str;
stack<node> s;//保存操作符
queue<node> q;//保存后缀表达式
map<char,int> op;//对应操作符及其优先级
//将中缀表达式转换为后缀表达式
void Change(){
int num;
node temp;
for(int i=0;i<str.length();){
if(str[i]>='0'&&str[i]<='9'){//是数
temp.flag=true;
temp.num=str[i++]-'0';//char转int
q.push(temp);//将此操作数压入后缀表达式队列
}
else{//是操作符
temp.flag=false;
//只要操作符栈的栈顶元素优先级比该操作符高，就把栈顶元素弹出到后缀表达式队列
while(!s.empty()&&op[str[i]]<=op[s.top().op])
{
q.push(s.top());
s.pop();
}
temp.op=str[i];
s.push(temp);//把该操作符压入栈
i++;
}
}
//若栈中还有操作符，就将它弹出到后缀表达式队列
while(!s.empty()){
q.push(s.top());
s.pop();
}
}
//计算后缀表达式
int Cal(){
int temp1,temp2;
node cur,temp;
while(!q.empty()){
cur=q.front();//记录队首元素
q.pop();
if(cur.flag==true){//若为操作数，压入栈
s.push(cur);
}
else{
temp2=s.top().num;
s.pop();
temp1=s.top().num;
s.pop();
temp.flag=true;//记录计算后的操作数
if(cur.op=='+'){
temp.num=temp1+temp2;
}
else if(cur.op=='-'){
temp.num=temp1-temp2;
}
else if(cur.op=='x'){
temp.num=temp1*temp2;
}
else{
temp.num=temp1/temp2;
}
s.push(temp);//把该操作数压入栈
}
}
return s.top().num;
}
int main(){
op['+']=op['-']=1;//设置操作符的优先级
op['x']=op['/']=2;
int n;
cin>>n;
int a[n];//保存每个计算的结果
for(int i=0;i<n;i++){
cin>>str;
while(!s.empty()){//初始化栈
s.pop();
}
Change();
a[i]=Cal();
}
for(int j=0;j<n;j++){
if(a[j]==24){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
队列
两次遍历，第一次遍历整个表达式先求解出所有乘除法的结果，存储加减号和加减操作数；第二次同时遍历两个队列求解出所有加减法的结果。为此，可以定义两个队列：
-
queue
num：存储加减法的操作数和乘除法的结果 -
queue
op：存储+、-符号
为了编码方便，可以在每一个表达式的末尾添加上+0字符，最终结果不变，但是编码会方便很多。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
string s;
cin>>n;
queue<int>num;//存储加减法的操作数和乘除法的结果
queue<char>op;//存储+、-符号
while(n--){
cin>>s;//s存储表达式
s.push_back('+');//在每个表达式末尾加上"+"字符
for(int i=1;i<s.size();i+=2){//遍历整个字符串
int t=s[i-1]-'0';//t存储乘除结果数字
for(;i<s.size()&&s[i]=='x'||s[i]=='/';i+=2){//求出连续乘除运算的结果
t=(s[i]=='x')?t*(s[i+1]-'0'):t/(s[i+1]-'0');
}
num.push(t);//数字进入队列
op.push(s[i]);
}
num.push(0);//加减法操作数再放入一个0，保证在整个表达式末尾添上了+0运算
int t=num.front();//第一个加减法操作数
num.pop();
while(!op.empty()){//同时遍历两个队列，求出加减运算的结果
char c=op.front();
op.pop();
t=(c=='+')?t+num.front():t-num.front();
num.pop();
}
puts(t==24?"Yes":"No");
}
return 0;
}
