任务描述
本关任务：计算逆波兰表达式的值。
相关知识
放苹果问题
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：5，1，1和1，5，1 是同一种分法。
我们可以先假设有一个函数count(m,n)能告诉我们m个苹果放n个盘子有多少种放法，然后在此基础上进行分析：
根据m和n之间的关系，可以分成以下两种情况来讨论：
①. 如果m小于n，即苹果（m）数比盘子（n）数小，那么无论怎么放，总是会至少有n - m个空盘子。因此可以得到：count(m,n) = count(m,m)。
②. 如果m大于等于n，即苹果数比盘子数多，或者相同，则有两种放置方法：
所有盘子都要放苹果。这个时候苹果中的**n个的位置已经固定**，只要考虑剩下m-n个，因此可以得到：count(m,n) = count(m - n,n)。
有盘子不放苹果。在这种情况中，我们可以只考虑有一个盘子不放。因为在不断的往下递的过程中，盘子数可以不断的减一，隐含了在m个苹果放在n - 1 ,n - 2 ... 2 ,1个盘子中的情况。这个时候可以得到count(m,n) = count(m,n - 1)。
综合以上两点，可以得到代码：
int count(int m,int n)
{
if(m < n)
return count(m,m);
else
return count(m - n,n) + count(m,n - 1); //两种放置方法的和
}
现在还差一个终止条件。考虑盘子数或者苹果数各为1或者0时，有：
盘子数为0或者1，苹果无论有多少都只有一种分配方法。
苹果数为0或者1，无论如何都只能放在一个盘子里。
即得到：
if(m <=1 || n <= 1)
return 1;
上下两段代码组合起来，就得到：
int count(int m,int n)
{
if(m <=1 || n <= 1)
return 1;
if(m < n)
return count(m,m);
else
return count(m - n,n) + count(m,n - 1); //两种放置方法的和
}
当我们输入2 2时，即count(2,2)，得到的结果是：
2
即两种放法：每个盘子放一个苹果，或者两个苹果放在一个盘子里。
总的来说，利用递归进行自动分析的方法如下：
先假设有一个函数能给出答案。
再利用这个函数，分析如何解决问题。
搞清楚最简单的情况下答案是什么。
编程要求
逆波兰表达式是一种把运算符前置的算术表达式，如：
2 + 3的逆波兰表示法为+ 2 3。
(2 + 3) * 4的逆波兰表示法为* + 2 3 4。
现在请你编写一个程序，读取一段正确的逆波兰表达式，计算并输出它的结果。
输入的表达式中只有+ - * /四种运算符，且数字均为**1位，但是运算时要按照浮点数float**来运算。
请在右侧编辑器的Cal函数中，读取输入的逆波兰表达式，计算并输出结果，占一行。
输入数据需要学员自己读取。具体见测试说明。
测试说明
平台会对你编写的代码进行测试：
预期输入：+ 2 3
预期输出：5
预期输入：* + 2 3 4
预期输出：20
参考代码：
#include <iostream>
#include <cstdlib>
using namespace std;
/********** Begin **********/
//可以在此增加其他函数
float exp() {
char s[20];
cin >> s;
switch (s[0]) {
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return atof(s);
}
}
void Cal() {
//在此补充代码完成函数功能
cout << exp() << endl;
}
/********** End **********/