【CCF】201903-2 -二十四点

1.题目

2.思路分析

首先，需要把加减号处理掉。根据运算符号的性质，输入了一个式子后，当我们读取字符，读到乘号或者除号时，运算符两边的数字就可以进行计算了。我们可以采用栈来实现，将每一个数字（处理好加减）入栈，遇到乘除法，弹出栈顶，计算结果之后再返回栈，最后，将栈内的所有元素弹出，加起来即可。

3.代码实现

#include <iostream>
#include <stack>
using namespace std;

int Pocess(string str)
{
	stack<int>s;
	int len = str.size();
	int flag = 1;//初始化flag 
	for(int i=0; i<len; i++)
	{
		if(str[i]>='0' and str[i]<='9')
		{
			//是数字，入栈
			s.push((str[i]-'0')*flag);
		}
		else if(str[i]=='-' or str[i]=='+')
		{
			//处理加减号，将他们和后面的数字合并作为一个，即对flag修改
			if(str[i]=='-')
				flag = -1;
			else
				flag = 1;	
		}
		else//乘除号
		{
			int ans = s.top();//取出栈顶元素准备计算 
			s.pop();	//弹出栈顶元素
			int temp;
			if(str[i]=='x')
			{
				temp = ans*(str[i+1]-'0');	
			}
			else
			{
				temp = ans/(str[i+1]-'0');
			}
			s.push(temp);//将结果入栈
			//此时已经处理好了i+1位的数字了
			//接下来要处理i+2位，所以i先要自增一次
			i++; 
		} 
	}
	int val = 0;
	while(!s.empty())//将每个部分的结果取出来相加得到整个等式的结果
	{
		int t = s.top();
		val = val + t;
		s.pop();
	}
	return val;
}
int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		string str;
		cin >> str;
		int re = Pocess(str);
		if(re==24)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;	
} 

4.总结

这道题目总的思路就是，根据加号、减号将式子分块计算各个部分的结果，如果遇到了乘除号，就将两边的数字进行计算作为一块。
例如，3x4+5+6，在得到结果之前，栈中有三个元素，12,5，6。3x4作为了一个整体。
这道题使用栈实现非常巧妙，研究许多用栈做的题，会发现很多类似的地方。这为之后的做题提供了方便。