当前位置：首页 > news >正文

CSP-CCF★★★201903-2二十四点★★★

news 2024/11/20 9:22:20

一、问题描述

二、解答

方法一：穷举法（只列举了一部分）

方法二：中缀表达式直接求值，两个栈，一个存放数值，一个存放符号

方法三：将中缀表达式转换为后缀来计算注意：

三、总结

一、问题描述

二、解答

方法一：穷举法（只列举了一部分）

即将所有的情况列举出来，共4*4*4=64种情况,但是我实在列不下去了，就只列举了12种。

建造了一个结构体，里面存放输入的字符串；使用两个vector容器，分别存放数字和符号；另外还弄了一个字符串数组，来存放每行结果yes或no。

注意：string不需要显式初始化，且字符串应该使用双引号。

代码（没有写完）：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Data {string s;
}str[100];
int main()
{int n;cin >> n;//string str[100];for (int i = 0; i <n; i++){//string s;cin >> str[i].s;}vector<int>a;int m=0;vector<char>b;//string stri[100] = { NULL };string stri[100];//string不需要显式初始化for (int i = 0; i < n; i++){a.clear();//先对vector容器进行清空b.clear();int sum = 0;for (int j = 0; j <= 6; j++)//字符串一共7个，所以j是小于等于6或者小于7，别再犯低级错误了！！！{if (j % 2 == 0){m = str[i].s[j] - '0';a.push_back(m);}else {b.push_back(str[i].s[j]);}	}//共4*4*4=64种情况,实在列不下去了，就列举了12种if (b[0] == '+' && b[1] == '+' && b[2] == '+') {sum = a[0] + a[1] + a[2] + a[3];}if (b[0] == '+' && b[1] == '+' && b[2] == '-') {sum = a[0] + a[1] + a[2] -a[3];}if (b[0] == '+' && b[1] == '+' && b[2] == 'x') {sum = a[0] + a[1] + a[2] *a[3];}if (b[0] == '+' && b[1] == '+' && b[2] == '/') {sum = a[0] + a[1] + a[2] / a[3];}if (b[0] == '+' && b[1] == '-' && b[2] == '+') {sum = a[0] + a[1] - a[2] + a[3];}if (b[0] == '+' && b[1] == '-' && b[2] == '-') {sum = a[0] + a[1] - a[2] - a[3];}if (b[0] == '+' && b[1] == '-' && b[2] == 'x') {sum = a[0] + a[1] - a[2] * a[3];}if (b[0] == '+' && b[1] == '-' && b[2] == '/') {sum = a[0] + a[1] - a[2] / a[3];}if (b[0] == '+' && b[1] == 'x' && b[2] == '+') {sum = a[0] + a[1] * a[2] + a[3];}if (b[0] == '+' && b[1] == 'x' && b[2] == '-') {sum = a[0] + a[1] * a[2] - a[3];}if (b[0] == '+' && b[1] == 'x' && b[2] == 'x') {sum = a[0] + a[1] * a[2] * a[3];}if (b[0] == '+' && b[1] == 'x' && b[2] == '/') {sum = a[0] + a[1] * a[2] / a[3];}if (sum == 24){//stri[i] = 'Yes';stri[i] = "Yes";}else {//stri[i] = 'No';stri[i] = "No";}}for (int i = 0; i < n; i++) {cout << stri[i] << endl;}return 0;
}

方法二：中缀表达式直接求值，两个栈，一个存放数值，一个存放符号

思路可以参考之前写过的博客：栈的应用之表达式求值（前缀、中缀、后缀）-CSDN博客

注意：

①循环条件：栈外元素比栈顶元素优先级小或相等+栈不为空，两个条件才能继续循环

②关于报错：back() called on empty deque：应该先检查栈是否为空，再写其他条件。

✘while (pri(s[j]) <= pri(top)||optr.empty()==true)
循环条件是：栈外元素比栈顶元素优先级小或相等+栈不为空，两个条件才能继续循环，所以不应该是||，而是&&。
✘while (pri(s[j]) <= pri(optr.top())&&!optr.empty())
后判空，也是错误的。应该先判空！！！
✔while (!optr.empty()&&pri(s[j]) <= pri(optr.top()))

③这里栈不清空不影响，因为只要是看运算符的栈，每次循环结束后，这个栈都是空的。

代码：

#include<iostream>
#include<stack>
using namespace std;
int pri(char op) {//设置优先级if (op == 'x' || op == '/') {return 2;}else if (op == '+' || op == '-') {return 1;}
}
int comp(char op, int x, int y) {//计算switch (op){case '+':return x + y; break;case '-':return x - y; break;case 'x':return x * y; break;case '/':return x / y; break;default:break;}
}
int main()
{int n;cin >> n;string s;stack<int>opnd;//存放数字stack<char>optr;//存放符号string str[100];//存放结果for (int i = 0; i < n; i++){cin >> s;int res = 0;for (int j = 0; j <7; j++){if (s[j] > '0' && s[j] <= '9'){opnd.push(s[j] - '0');}else {if(optr.empty())//栈为空{optr.push(s[j]);}else {if (pri(s[j]) > pri(optr.top())) {optr.push(s[j]);}else {//while (pri(s[j]) <= pri(top)||optr.empty()==true)//栈外元素比栈顶元素优先级小或相等+栈不为空，两个条件才继续循环//while (pri(s[j]) <= pri(optr.top())&&!optr.empty())// 后判空，也是错误的。应该先判空！！！	while (!optr.empty()&&pri(s[j]) <= pri(optr.top()))						{int p = opnd.top();opnd.pop();int q = opnd.top();opnd.pop();//注意这里是：次栈顶元素加减乘除栈顶元素！！！int result = comp(optr.top(), q, p);opnd.push(result);optr.pop();							}optr.push(s[j]);}}}}//遍历结束后while (!optr.empty()){char top = optr.top();int p = opnd.top();opnd.pop();int q = opnd.top();opnd.pop();res= comp(top, q, p);opnd.push(res);optr.pop();}if (res == 24) {str[i] = "Yes";}else {str[i] = "No";}}for (int i = 0; i < n; i++) {cout << str[i] << endl;}return 0;
}

方法三：将中缀表达式转换为后缀来计算
注意：

①在使用STL容器涉及循环时，最好应该在每一次循环开始前清空，否则影响下一次循环。

②使用到的两个栈的数据类型是不一样的，注意字符和数字之间的转换。

思路：可参考之前写过的博客栈的应用之表达式求值（前缀、中缀、后缀）-CSDN博客

代码：

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int pri(char op) {//设置优先级if (op == 'x' || op == '/') {return 2;}else if (op == '+' || op == '-') {return 1;}
}
int comp(char op, int x, int y) {//计算switch (op){case '+':return x + y; break;case '-':return x - y; break;case 'x':return x * y; break;case '/':return x / y; break;default:break;}
}
int main()
{int n;cin >> n;string s;stack<char>st1;//用来将中缀转换为后缀，存放符号stack<int>st2;//用来对后缀求值，存放数字,为int型vector<char>v;//用来存放后缀表达式string str[100];//存放结果for (int i = 0; i < n; i++) {cin >> s;int result = 0;//将中缀转换为后缀for (int j = 0; j < 7; j++){			if (s[j] > '0' && s[j] <= '9') {v.push_back(s[j]);}else {if (st1.empty()) {st1.push(s[j]);}else {if (pri(s[j]) > pri(st1.top())) {st1.push(s[j]);}else {while (!st1.empty() && (pri(s[j]) <= pri(st1.top()))){v.push_back(st1.top());st1.pop();}st1.push(s[j]);}}}}//遍历结束后while (!st1.empty()) {v.push_back(st1.top());st1.pop();}//对后缀求值for (vector<char>::iterator it = v.begin(); it != v.end(); it++){if (*it > '0' && *it <= '9'){int m = *it - '0';st2.push(m);}else {int p = st2.top() ;st2.pop();int q = st2.top();st2.pop();result = comp(*it, q, p);//char c = result + '0';st2.push(result);//注意这里要加‘0’}}if (result == 24) {str[i] = "Yes";}else {str[i] = "No";}while(!st2.empty()){st2.pop();}v.clear();}for (int i = 0; i < n; i++) {cout << str[i] << endl;}return 0;
}