CCF-201903-2-二十四点
CCF题目
成功案例
主函数
//输入数据的主函数
int main() {
int n;
cin >> n;
string str[100];
for (int i = 0; i < n; i++) {
char s[6];
cin >> s;
str[i] = s;
}
for (int i = 0; i < n; i++) {
int ans = jisuan(str[i]);
if (ans == 24) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}计算方法
了解了前缀表达式，中缀表达式，后缀表达式的相关定义后，就明白了。
核心计算方法是把减号换成负数相加，对乘号和除法直接计算结果，最后累和得到结果！
数据结构上使用了栈，理论是是逆波兰式，对后缀表达式进行的遍历操作。
有人说逆波兰式和波兰式是有区别的，但是核心都是扫描到两个数值与一个运算符进行运算，结果压栈继续反复。
请原谅我区分不出来两者的区别。
//计算字符串str对应的结果
int jisuan(string str) {
stack<int> sint;
for (int i = 0; i < 7; i++) {
if (str[i] == '+') {
} else if (str[i] == '-') {
sint.push('0' - str[i + 1]);
i = i + 1;
continue;
} else if (str[i] == 'x') {
int t = sint.top() * (str[i + 1] - '0');
sint.pop();
sint.push(t);
i = i + 1;
continue;
} else if (str[i] == '/') {
int t = sint.top() / (str[i + 1] - '0');
sint.pop();
sint.push(t);
i = i + 1;
continue;
} else {
sint.push(str[i] - '0');
}
}
int sum = 0;
while (sint.size() > 0) {
sum += sint.top();
sint.pop();
}
return sum;
}失败过程
思路一(失败)
主函数
先简单的把主函数写出来，还是从txt文档里输入数据，用数组保存信息之后，建立对应的函数，完成第一步操作。
#include<iostream>
#include <fstream>
#include<string>
#include <stack>
using namespace std;
int main() {
ifstream fin("1.txt");
if (!fin) {
return -1;
}
int n;//一共多少组算式
fin >> n;
string *str = new string[n];
for (int i = 0; i < n; i++) {
fin >> str[i];
}
for (int i = 0; i < n; i++) {
cout << judge_4(str[i]) << endl;
}
fin.close();
return 0;
}计算函数体
建立judge_4函数体。
string judge_4(string s) {
stringstream ss;//方便类型转换
double a, b, c, d;//四个数值
char ch;//临时记录
string temp = "";//临时记录
string str = "";//进行一次计算后,还保留了三个数值和两个运算符
ch = s[0] - '0';
a = ch;
ch = s[2] - '0';
b = ch;
ch = s[4] - '0';
c = ch;
ch = s[6] - '0';
d = ch;
if (s[1] == 'x' || s[1] == '/') {
if (s[1] == 'x') {//进行运算
a = a * b;
} else {
a = a / b;
}
ss << a;//类型转换
temp = ss.str(); //完成类型转换
str += temp;
str += s.substr(3);
} else if (s[3] == 'x' || s[3] == '/') {
if (s[3] == 'x') {
b = b * c;
} else {
b = b / c;
}
ss << b;//类型转换
temp = ss.str(); //完成类型转换
str += s.substr(0, 2);
str += temp;
str += s.substr(5);
} else if (s[5] == 'x' || s[5] == '/') {
if (s[5] == 'x') {
c = c * d;
} else {
c = c / d;
}
ss << c;//类型转换
temp = ss.str(); //完成类型转换
str += s.substr(0, 4);
str += temp;
}
if (str == "") { //没有进行乘除运算
if (s[1] == '+') {
a = a + b;
} else {
a = a - b;
}
ss << a;//类型转换
temp = ss.str(); //完成类型转换
str += temp;
str += s.substr(3);
}
return str;
}测试后成功达成目的。
但是照猫画虎做出来judge_3之后却发现一个缺陷，就是我一开始是直接按照下标去寻找运算符的，但是在进行过一步运算之后发现，部分数值变成了两位的，于是运算符下标也就改变了，所以，应该使用string的STL函数find_first_of来记录对应运算符的位置。
但是紧接着就要面对如果出现同一个运算符多次出现的时候，其后出现的下标就很难记录了。
同样的，如果数字不是一位的而是多位的，又要怎么记录呢？
所以，更换思路。
思路二(失败)
首先需要记录数字，不能够使用简单的下标对应了。因为如果出现了形如365*987之类的，就没办法操作了。
主函数
同样的，参考思路一的主函数。不再赘述。
首先读取数字
返回的ans是数值，k是紧接着的运算符
int get_num(string str, int &k) { // 从k开始一直读所有的数字字符
int ans = 0;//记录数值
char chh = str[k];//记录第一个字符,后面判断是否是负号
if (str[k] >= '0' && str[k] <= '9')
ans = ans * 10 + str[k] - '0';
k++;
for (; k < str.size(); k++) {
if (str[k] >= '0' && str[k] <= '9')
ans = ans * 10 + str[k] - '0';
else break;
}
// 此时的k是之后的运算符下标
k--;//对应在judge_2函数体里的i++
if (chh == '-') {
return ans * (-1);
} else {
return ans;
}
}读取运算符之后分别保存起来
string judge_3(string s) {
stack<double> s;//为了防止出现4/5的情况
int a, b, c, d;//四个数值
int k = 0;//辅助记录下标的
string str = "";
int arr[3] = {0, 0, 0};//记录运算符的,加减乘除,对应1,2,3,4
a = get_num(s, k);
arr[0] = s[k];
b = get_num(s, k);
arr[1] = s[k];
c = get_num(s, k);
arr[2] = s[k];
d = get_num(s, k);
return str;
}此路不通
最后对应的去判断是否压入堆栈还需要另一遍的遍历，就觉得好繁琐，肯定是有更合适的思路。如果一边找数值一边压入堆栈呢？
思路三(失败)
主函数和数值查询
参考思路一和思路二
我想把运算符判断和最后的堆栈压入结合在一起，于是在网上参考资料，找到了新思路。
最后的函数体
函数体judge_2来完成压栈判断以及最后的累和
string judge_2(string s){
stringstream ss;
stack<double> st;//为了防止出现4/5的情况
string str="";
int num;//保存数值的临时量
char ch;//保存运算符的临时量
for (int i=0;i<s.size();i++) {//i辅助记录下标的
if ((s[i]>='0'&&s[i]<='9')||s[i]=='-'||s[i]=='+') {//是正是负或者是数值
num=get_num(s,i);
st.push((double)num);
}
else {
ch=s[i];
double x1=st.top();
st.pop();
double x2=get_num(s,i);
if (ch=='x')
st.push((double)x1*(double)x2);
else
st.push((double)x1/(double)x2);
}
}
int sum=0;
while (!st.empty()) {
sum+=st.top();
st.pop();
}
if(sum==24){
str="YES";
}else{
str="NO";
}
// ss<<sum;
//
// str=ss.str();
return str;
}在这里能够成功的运行出来想要的结果！
内心里泪流满面！
但是测试之后...
空间太大爆掉了？
我试了试我参考的代码，切，原来他的也过不去....
最后还是我找伙伴寻求帮助，终于能够通过了！
感谢
从今以后，所有刷题的文章都是先写正确的在前面，后面再附上我之前的思考和失败过程。
源码文件：
gitee：https://gitee.com/JunKuangKuang/KeenCPPTest-all/tree/main/ccf/2019-03/2
github：https://github.com/JunKuangKuang/KeenCPPTest-all/tree/main/ccf/2019-03/2
感谢现在努力的自己。
感谢俺的亲亲舍友，诶嘿嘿嘿
第十六次 ccf 201903-2 二十四点，这篇文章里还写了如果遇到括号怎么办！
波兰式、逆波兰式与表达式求值，可以读读了解基础知识
