第一题：逆波兰表达式求值
1.题目
掌握递归的基本语法和思想，利用递归程序实现逆波兰表达式，并分析算法复杂度。
2.问题分析与算法设计思路
这里实现了对多位数整的操作，运算仅包含四则运算。输入中使用.来将不同的操作数隔开，使用@表示表达式的结束。
使用栈的实现方法在另一篇博客中写过，请参考：计算后缀表达式-算法与数据结构-栈的运用-C++语言实现。这里我们将使用递归的方法来实现（虽然也用到了栈，但仅仅是为了从尾部开始读取字符而已）。
思路：
每个操作符将需要两个操作数，可以为表达式构建一颗递归树，每个操作数可能就是表达式中的一个数字，也可能要由一个子表达式（递归就来了）计算得到。
以输入3.5.2.-*7.+@为例，构建递归树：
注意：
由于我是从表达式的尾部开始读取字符，而减法、除法运算并不满足交换律，因此需要额外调整一下。
遇到问题：
再调试过程中遇到了一个很奇怪的问题，我现在仍没有弄清楚原理，我将它记录在问答社区：有个带函数的表达式前加负号无效。在下面的代码中，采用了避免该问题的写法。
3.算法实现
//逆波兰表达式——递归 #include<iostream> #include<cstdio> #include<stack> using namespace std; stack<char> s; int get_num(){//从栈中返回一个整型数字 char t=0; int sum=0; for(int i=1; ! s.empty(); i *= 10){ t = s.top(); if('0' <= t && t <= '9'){ s.pop(); sum += (t - '0') * i; } else break; } //cout<<"sum "<<sum<<endl; return sum; } int nbl(char x){//对逆波兰表达式求值 if(x == '+' || x == '-' || x == '*' || x == '/'){ s.pop(); if(x == '+'){ int t = nbl(s.top()) + nbl(s.top()); cout<<"t: "<<t<<endl; return t; } else if(x == '-'){ int t = (nbl(s.top()) - nbl(s.top())); t = -t; cout<<"t: "<<t<<endl; return t; } else if(x == '*'){ int t = nbl(s.top()) * nbl(s.top()); cout<<"t: "<<t<<endl; return t; } else if(x == '/'){ int t = (int)(1 / ((double)nbl(s.top()) / nbl(s.top()))); cout<<"t: "<<t<<endl; return t; } } else if(x == '.'){ s.pop(); return get_num(); } } int main(){ char t='0'; while(true){ cin >> t; if(t == '@') break; s.push(t); } if(s.empty()){ cout<<"表达式为空"<<endl; } else cout<<nbl(s.top()); return 0; } /* 测试数据 3.5.2.-*7.+@ 10.28.30./*7.-6.+@ 1000.1000./5.-6.*@ */
代码更新（9月19日）：
改变了函数nbl()中不同四则运算分支的代码写法，这样看起来更加简洁和明确，调试时查看中间结果也更加的方便。
//逆波兰表达式——递归 #include<iostream> #include<cstdio> #include<stack> using namespace std; stack<char> s; int get_num(){//从栈中返回一个整型数字 char t=0; int sum=0; for(int i=1; ! s.empty(); i *= 10){ t = s.top(); if('0' <= t && t <= '9'){ s.pop(); sum += (t - '0') * i; } else break; } return sum; } int nbl(char x){//对逆波兰表达式求值 s.pop(); if(x == '+' || x == '-' || x == '*' || x == '/'){ if(x == '+'){ int a = nbl(s.top()); int b = nbl(s.top()); return a + b; } else if(x == '-'){ int a = nbl(s.top()); int b = nbl(s.top()); return b - a; } else if(x == '*'){ int a = nbl(s.top()); int b = nbl(s.top()); return a * b; } else if(x == '/'){ int a = nbl(s.top()); int b = nbl(s.top()); return b / a; } } else if(x == '.'){ return get_num(); } } int main(){ char t='0'; while(true){ cin >> t; if(t == '@') break; s.push(t); } if(s.empty()){ cout<<"表达式为空"<<endl; } else cout<<nbl(s.top()); return 0; }
4.运行结果
输出的t为每次四则运算得到的中间结果。
5.算法分析
算法的时间复杂度应为：o ( n ) o(n)o(n)，其中 n 为输入表达式的长度。
第二题：Fibonacci数列的尾递归与非递归程序
1.题目
将Fibonacci数列的递归求解方法转为尾递归求解；借助栈实现递归转非递归程序。
2.问题分析与算法设计思路
主要是学会可递归问题的多种写法。
3.算法实现
一、尾递归
关于使用尾递归，可以参考一下：尾递归实现斐波那契数
//斐波那契尾递归实现 #include<iostream> using namespace std; int fbnq(int n, int a, int b){ //b表示当前值，a表示前一项的值。其实类似于循环迭代，n控制循环次数 if(n == 1) return b; return fbnq(n-1, b, a+b); } int main(){ int n = 0; cout<<"求斐波那契数列的第多少项？"<<endl; while(n < 1){ cin >> n; } cout<<fbnq(n, 0, 1); return 0; }
二、使用栈的非递归
//斐波那契使用栈非递归实现 #include<iostream> #include<stack> using namespace std; stack<int> s; int main(){ int n = 0; int a = 0; int b = 0; cout<<"求斐波那契数列的第多少项？"<<endl; while(n < 1){ cin >> n; } s.push(0); s.push(1); for(int i = 0; i < n - 1; i++){ a = s.top(); s.pop(); b = s.top(); s.pop(); s.push(a); s.push(a+b); } b = s.top(); cout<<b; return 0; }
4.运行结果
5.算法分析
算法复杂度为：o ( n ) o(n)o(n)。
这里的递归写法时间开销要比非递归大一些（即使不考虑递归操作本身的原因），因为会存在重复计算。例如递归计算f ( 5 ) f(5)f(5)，则需要计算f ( 4 ) f(4)f(4)和f ( 3 ) f(3)f(3)，而计算f ( 4 ) f(4)f(4)中又计算了一次f ( 3 ) f(3)f(3)。这个问题据说可以用记忆化进行优化，但我还没有实操尝试过。
