鱼C论坛

 找回密码
 立即注册
查看: 4968|回复: 40

[已解决]程序制作时的一个问题,请大佬求助

[复制链接]
发表于 2022-10-15 06:50:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zhangjinxuan 于 2022-10-15 21:07 编辑

最近在做24点计算器,计算的函数写好了,但是有一个问题,返回的表达式得从左往右计算才可得到结果24

运行实况:
请输入数字个数:4
请输入4个数字:1 2 3 4
此题有解,解法是:1+2+3*4

1+2+3*4,它算出来的结果应该是15,但我想让它算出来的结果是24,就只能这样去加括号:
(1+2+3)*4
但仍然有问题,我该怎么去实现啊?

昨晚盯着一个算式盯了1个小时都没有想出来

如果题目还不理解,那就理解为:
给你一个表达式,在表达式中添加一些括号(不能添加多余的括号),使这个表达式与从左往右计算的表达式结果相同
样例1:
输入:5*8-6*7
输出:(5*8-6)*7
样例2:
输入:9-8*1*8-6/2
输出:(9-8)*1*(8-6)/2
最佳答案
2022-10-15 16:06:41
本帖最后由 dolly_yos2 于 2022-10-15 16:10 编辑

可以测试一下看看是不是这个意思(总觉得写复杂了)(假设操作数总在 int 范围内、输入总是以操作数开始、除最后一个操作数外每个操作数后总是紧接着一个四则运算符、每个四则运算符后总是紧接着一个操作数、输入中没有任何其他符号)
#include <iostream>
#include <vector>
void parse_helper(
        const std::vector<int>& operands,
        const std::vector<char>& operators,
        const size_t level,
        std::ostream& output
){
        bool issue_parentheses = false;
        if(level > 0){
                if(!(operators.at(level) & 4u) && (operators.at(level - 1) & 4u)){
                        issue_parentheses = true;
                        output.put('(');
                }
                parse_helper(operands, operators, level - 1, output);
        }else{
                output << operands.at(0);
        }
        if(issue_parentheses) output.put(')');
        output.put(operators.at(level) - 1);
        output << operands.at(level + 1);
}
void parse(std::istream& input, std::ostream& output){
        std::vector<int> operands;
        std::vector<char> operators;
        int value;
        char op;
        input >> value;
        operands.emplace_back(value);
        while(true){
                input >> op >> value;
                if(input.eof()) break;
                operands.emplace_back(value);
                operators.emplace_back(op + 1);        // 一个小小的 trick 来简化算符优先级判断
                                                // 考虑到 ASCII 下四则运算符的码值分别为
                                                //  * -- 0x2A (00101010)
                                                //  + -- 0x2B (00101011)
                                                //  - -- 0x2D (00101101)
                                                //  / -- 0x2F (00101111)
                                                // 给码值加一后可见高优先级运算符的第三低有效位(从一开始)
                                                //  均为 0 而低优先级的均为 1
        }
        parse_helper(operands, operators, operators.size() - 1, output);
}
int main(){
        parse(std::cin, std::cout);
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-10-15 06:58:02 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 07:47:05 | 显示全部楼层

回帖奖励 +2 鱼币

本帖最后由 jhq999 于 2022-10-15 08:01 编辑

有个想法
把9-8*1*8-6/2切成不同长度的小段
9-|(9-8)* |(9-8*1)*|(9-8*1*8)-|(9-8*1*8-6)/
8*|8*1*|8*1*8-|(8*1*8-6)/|(8*1*8-6/2)
1*|1*8-|(1*8-6)/|(1*8-6/2)
8-|(8-6)/|(8-6/2)
6/|6/2
2
然后组合
(9-8*1*8-6)/2
(9-8*1*8)-6/2
(9-8*1)*(8-6/2)      (9-8*1)*(8-6)/2     (9-8*1)*8-6/2
.........
9-8*1*(8-6)/2
然后逆波兰计算
不成熟的想法仅供参考
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 07:52:17 | 显示全部楼层
精简括号:每个小段如果有加减,而且上一个后面有乘除或者对下一小段有乘除保留括号,否则去掉括号
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 08:02:06 | 显示全部楼层
jhq999 发表于 2022-10-15 07:52
精简括号:每个小段如果有加减,而且上一个后面有乘除或者对下一小段有乘除保留括号,否则去掉括号

最好给出代码,谢谢大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 08:24:33 | 显示全部楼层

回帖奖励 +2 鱼币

我去  , 这是绿题啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 08:26:36 | 显示全部楼层
柿子饼同学 发表于 2022-10-15 08:24
我去  , 这是绿题啊

有思路吗,我真的急
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 08:48:58 | 显示全部楼层

回帖奖励 +2 鱼币

我感觉不一定是可以通过从左往右的计算可以的出来,比如4*5+4*1这种式子,所以我感觉你这个思路不太对,应该建一个树,一次拉两个元素进行运算(其实这样就更麻烦了)

评分

参与人数 1鱼币 +1 收起 理由
zhangjinxuan + 1 谢谢回帖

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 08:59:14 | 显示全部楼层
zhangjinxuan 发表于 2022-10-15 08:57
我的思路是,用一个深搜求出算式,但是算式必须从左往右计算才可得到24,我就想加一些括号,既能按照平时 ...

我的意思是这种方法可能不一定能够求出答案,因为会有那种必须是不按照顺序的算式
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:03:24 | 显示全部楼层
tommyyu 发表于 2022-10-15 08:59
我的意思是这种方法可能不一定能够求出答案,因为会有那种必须是不按照顺序的算式

你看看代码,我也解释不清楚
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 09:04:23 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:07:17 | 显示全部楼层
人造人 发表于 2022-10-15 09:04
这个怎么样?
https://blog.csdn.net/smartboysboys/article/details/20765427

let me see see...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:08:02 | 显示全部楼层
人造人 发表于 2022-10-15 09:04
这个怎么样?
https://blog.csdn.net/smartboysboys/article/details/20765427

不要枚举算法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 09:11:47 | 显示全部楼层

                void dfs(int i, int s) { //深搜找答案
你这dfs和枚举有何区别?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:13:33 | 显示全部楼层
人造人 发表于 2022-10-15 09:11
void dfs(int i, int s) { //深搜找答案
你这dfs和枚举有何区别?

你看,你看,你仔细看看吧,我真的急
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-15 09:16:54 | 显示全部楼层
zhangjinxuan 发表于 2022-10-15 08:57
我的思路是,用一个深搜求出算式,但是算式必须从左往右计算才可得到24,我就想加一些括号,既能按照平 ...


我这里有一个加括号的思路

可以给每一个算式一个等级,只有一个数的话(比如1、2、3、4)是2级

两个二级相加变为一级,不需要加括号
两个一级相加还是一级,也不需要加括号
一个二级和一个二级相加变为一级,也不需要加括号
二级减一级会变成一级,一级不需要加括号,但是需要变号
一级减二级变成一级,不需要加括号
二级乘二级还是二级,不需要加括号
二级乘一级还是二级,一级的式子需要加上括号
二级除以一级或一级除以二级还是二级,一级的式子需要加括号
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:19:44 | 显示全部楼层
tommyyu 发表于 2022-10-15 09:16
我这里有一个加括号的思路

可以给每一个算式一个等级,只有一个数的话(比如1、2、3、4)是2级

哎,都没有理解题面,语文表达才重要啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:26:28 | 显示全部楼层
tommyyu 发表于 2022-10-15 08:48
我感觉不一定是可以通过从左往右的计算可以的出来,比如4*5+4*1这种式子,所以我感觉你这个思路不太对,应 ...

不啊,(4*5+4)*1可以啊,但是你提醒了我,加括号前计算一下表达式,如果是24就不用加括号了,就直接返回表达式
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:27:01 | 显示全部楼层
编程题变成数学题了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 09:28:10 | 显示全部楼层
tommyyu 发表于 2022-10-15 08:59
我的意思是这种方法可能不一定能够求出答案,因为会有那种必须是不按照顺序的算式

请举例说明,我认为你说的那种必须是不按照顺序的算式调换一下数字位置就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 23:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表