CCF-201903-2-二十四点

CCF-201903-2-二十四点

CCF题目

样例1

样例2

成功案例

主函数

//输入数据的主函数
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;
}

在这里能够成功的运行出来想要的结果！

成功1

内心里泪流满面！

但是测试之后...

空间1

空间太大爆掉了？

我试了试我参考的代码，切，原来他的也过不去....

空间2

最后还是我找伙伴寻求帮助，终于能够通过了！

感谢

从今以后，所有刷题的文章都是先写正确的在前面，后面再附上我之前的思考和失败过程。

源码文件：

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 二十四点，这篇文章里还写了如果遇到括号怎么办！

波兰式、逆波兰式与表达式求值，可以读读了解基础知识