文档章节

求24点,算术式解析

梦想游戏人
 梦想游戏人
发布于 2016/10/26 15:36
字数 583
阅读 53
收藏 0

题目:

给定任意4个正整数,利⽤用加,减,乘,除,括号这⼏几个运算符,编程计
算所有由这4个数字计算出24的表达式,并输出计算表达式。
输出结果要求:加法,乘法需要去重,(( a + b ) * c) / d = 24 和 (( b + a)
* c ) / d = 24 视为同⼀一表达式,只输出任意⼀一个即可。
要求:请尝试⽤用测试驱动开发程序完成(TDD)
⽰示例1:
输⼊入:3 3 6 6
输出:((6/3)+6)*3 = 24
⽰示例2:
输⼊入:3 2 3 4
输出:⽆无解
⽰示例3:
输⼊入:5 5 6 6
输出:
((5+5)-6)*6 = 24
(5*5)-(6/6) = 24
((5-6)+5)*6 = 24
(5-(6-5))*6 = 24
(6-(6/5))*5 = 24

 

分析:

既然是TDD开发,那么先分析数据输出格式,4个数字,始终有2对括号,在这里并没有四则运算的优先级,都是用括号来表示运算顺序,因为4个数字要运算三次,所以2对括号就能完成,所以我们可以编写出一下算术表达式计算函数


class Opt
{
public:
	string type;
	int data = 0;
};


bool isOpt(string c)
{
	if (c == "+")return true;
	else if (c == "-")return true;
	else if (c == "*")return true;
	else if (c == "/")return true;
	else if (c == "(")return true;
	else if (c == ")")return true;
	else if (c == " ")return true;

	return false;
}





int cal(std::stack<Opt> & _s)
{
	if (_s.size() < 3)return 0;

	Opt op3 = _s.top(); _s.pop();
	Opt op2 = _s.top(); _s.pop();
	Opt op1 = _s.top(); _s.pop();
	if (!_s.empty())_s.pop();
	int res = 0;
	string c = op2.type;

	if (c == "+")
	{
		res = op1.data + op3.data;
	}
	else if (c == "-")
	{
		res = op1.data - op3.data;
	}
	else if (c == "*")
	{
		res = op1.data * op3.data;
	}
	else if (c == "/")
	{
		res = op1.data / op3.data;
	}

	return res;

}




int ParseExp(string exp)
{
	exp.append(" ");
	std::stack<Opt> _s;
	int isNum = 0;
	string nums;

	for (int i = 0; i < exp.size(); i++)
	{
		string opt;
		opt.push_back(exp[i]);
		//cout << opt << endl;
		if (isOpt(opt))
		{
			if (isNum != 0)
			{
				int num = 0;
				for (int k = 0, exp = 1; k < isNum; exp *= 10, k++)
				{
					Opt s = _s.top();

					num += exp* std::stoi(s.type);
					_s.pop();
				}
				Opt op;
				op.data = num;
				_s.push(op);
				isNum = 0;
			}

			if (opt == ")")
			{
				Opt op;
				op.data = cal(_s);
				_s.push(op);
			}
			else
			{
				Opt op;
				op.type = opt;
				_s.push(op);
			}


		}
		else
		{
			++isNum;
			Opt op;
			op.type = opt;
			_s.push(op);
		}

	}
	_s.pop();
	return  cal(_s);



}

int main()
{
	//int a = 3, b = 3, c = 6, d = 6;
	//string exp = "((5+5)-6)*6 ";

	cout << ParseExp("((6/3)+6)*3") << endl;;
	cout << ParseExp("((5+5)-6)*6") << endl;;
	cout << ParseExp("(5*5)-(6/6)") << endl;;
    cout << ParseExp("((55-55)+55)*1") << endl;;


	system("pause");

	return 0;
}

输出 24 24 24 55 ,计算结果正确

 

接下来我们就该生成所有组合 暴力算法 剪枝不可能的情况,不贴也罢(1.7 s左右)

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 38
博文 444
码字总数 127453
作品 0
成都
私信 提问
[深搜回溯]24点

题目描述: 24点是一个有趣的扑克牌游戏。发4张牌,然后计算是否能够算出24点来。(不考虑有括号的算式,输出计算式将从左到有进行计算) 如果可以,输出算数表达式; 如果不可以,输出NONE ...

肥宅_Sean
2017/11/01
0
0
编写程序实现快速计算《24点》这个游戏的答案

《24点》这个游戏的规则就是 很多人一起玩都可以,桌面上随意翻出4张牌,大家就利用这4张牌分别进行加减乘除运算,不能重复使用每张牌,谁最快算出结果等于24 就赢。 在程序的角度来讲,就是...

曾阿牛弟
2014/06/12
2.7K
1
常见的Javascript获取时间戳

为啥写这篇文章 最近在做项目的时候,发现获取时间戳的需求挺多的,通常是在做日期选择的时候,要拿开始时间和结束时间的时间戳。每次都得google一下,还不如自己搞一搞! 获取当前时刻的时间...

包子吃多会变蠢
2018/10/18
0
0
python 穷举法 算24点(史上最简短代码)

本来想用回溯法实现 算24点。题目都拟好了,就是《python 回溯法 子集树模板 系列 —— 7、24点》。无奈想了一天,没有头绪。只好改用暴力穷举法。 思路说明 根据四个数,三个运算符,构造三...

罗兵
2017/06/01
0
0
0059 PHP编程语言实现稍微复杂一些的例子程序

  上一节课用PHP编程语言实现了6个以前用Python实现过的程序。   这节课继续完成6个稍微复杂一些的例子程序。   星座判断程序   程序如下:      运行结果:      输入一个年...

零基础学编程
2018/10/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

容器服务

简介 容器服务提供高性能可伸缩的容器应用管理服务,支持用 Docker 和 Kubernetes 进行容器化应用的生命周期管理,提供多种应用发布方式和持续交付能力并支持微服务架构。 产品架构 容器服务...

狼王黄师傅
昨天
3
0
高性能应用缓存设计方案

为什么 不管是刻意或者偶尔看其他大神或者大师在讨论高性能架构时,自己都是认真的去看缓存是怎么用呢?认认真真的看完发现缓存这一块他们说的都是一个WebApp或者服务的缓存结构或者缓存实现...

呼呼南风
昨天
12
0
寻找一种易于理解的一致性算法(扩展版)

摘要 Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可...

Tiny熊
昨天
2
0
聊聊GarbageCollectionNotificationInfo

序 本文主要研究一下GarbageCollectionNotificationInfo CompositeData java.management/javax/management/openmbean/CompositeData.java public interface CompositeData { public Co......

go4it
昨天
3
0
阿里云ECS的1M带宽理解

本文就给大家科普下阿里云ECS的固定1M带宽的含义。 “下行带宽”和“上行带宽” 为了更好的理解,需要先给大家解释个词“下行带宽”和“上行带宽”: 下行带宽:粗略的解释就是下载数据的最大...

echojson
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部