CCF-CSP：201903-2二十四点

CCF-CSP题目汇总

题目

编号： 201903-2

试题名称： 二十四点

时间限制： 1.0s

内存限制： 512.0MB

题目背景

  二十四点是一款著名的纸牌游戏，其游戏的目标是使用3个加减乘除运算使得4张纸牌上数字的运算结果为24。

题目描述

  定义每一个游戏由4个从1-9的数字和3个四则运算符组成，保证四则运算符将数字两两隔开，不存在括号和其他字符，运算顺序按照四则运算顺序进行。其中加法用符号+表示，减法用符号-表示，乘法用小写字母x表示，除法用符号/表示。在游戏里除法为整除，例如2/3=0，3/2=1，4/2=2。
  老师给了你n个游戏的解，请你编写程序验证每个游戏的结果是否为24。

输入格式

  从标准输入读入数据。
  第一行输入一个整数n，从第2行开始到第n+1行中，每一行包含一个长度为7的字符串，为上述的24点游戏，保证数据格式合法。

输出格式

  输出到标准输出。
  包含n行，对于每一个游戏，如果其结果为24则输出字符串Yes，否则输出字符串No。

样例数据

样例1输入

10
9+3+4x3
5+4x5x5
7-9-9+8
5x6/5x4
3+5+7+9
1x1+9-9
1x9-5/9
8/5+6x9
6x7-3x6
6x4+4/5

样例1输出

Yes
No
No
Yes
Yes
No
No
No
Yes
Yes

样例1解释

  9+3+4×3=24
  5+4×5×5=105
  7-9-9+8=-3
  5×6/5×4=24
  3+5+7+9=24
  1×1+9-9=1
  1×9-5/9=9
  8/5+6×9=55
  6×7-3×6=24
  6×4+4/5=24

子任务

测试点	n	正确的游戏个数	包含的运算符
1	$=10^2$	$=10^2$	+,-,x,/
2	$=10^2$	$=0$	+,-,x,/
3，4	$=10^2$	$=50$	+
5，6	$=10^2$	$=50$	+,-
7，8	$=10^2$	$=50$	+,-,x
9，10	$=10^2$	$=50$	+,-,x,/

解答

分析

  分别使用运算数链表和操作符链表维护算式，在读取数据的时候遇到‘+’、‘—’和数字直接入列，遇到‘x’、‘/’的时候直接计算紧邻的两个数据，每次计算后的数据有重新入列。当遍历一遍算式以后乘、除高优先级运算符已经计算完成，剩下的算式中只剩下加、减运算，此时在按照从左到右的顺序依次出列数据、运算符计算再入列结果以便继续运算。最终当所有运算符都计算完成，操作符链表出列为空的时候，此时运算数链表仅剩一个数据，及最终结果。
  当然也可以直接使用逆波兰算法。

代码

#include <iostream>
#include <list>
#include <string>

using namespace std;

int main() {

	int n;//数据个数
	
	cin >> n;

	for (int j = 0; j < n; j++) {
		string str;//四则运算字符串
		list<int> num = list<int>();//运算数链表
		list<char> op = list<char>();//运算符链表

		cin >> str;

		for (int i = 0; i < 7; i++) {
			
			if (i == 0 || i == 2 || i == 4 || i == 6) {//i为偶数的时候，equ[i]为数字
				num.push_back(str.at(i)-'0');
			}
			else{
				if (str.at(i) =='+' || str.at(i) =='-'){//低优先级运算符直接入列
					op.push_back(str.at(i));
				}
				else{//高优先级运算符先进行运算,运算结果入列
					if (str.at(i) == 'x') {
						int t = num.back();
						num.pop_back();
						num.push_back(t*(str.at(++i) - '0'));
					}
					else{
						int t = num.back();
						num.pop_back();
						num.push_back(t/(str.at(++i) - '0'));
					}
				}
			}
		}

		//最后处理剩下的+、-运算符
		while (!op.empty()){
			if (op.front() == '+') {
				int t1 = num.front();
				num.pop_front();
				int t2 = num.front();
				num.pop_front();
				num.push_front(t2 + t1);
			}
			else{
				int t1 = num.front();
				num.pop_front();
				int t2 = num.front();
				num.pop_front();
				num.push_front(t1 - t2);
			}
			op.pop_front();
		}

		if (num.front() == 24) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

	return 0;
}