第一题：逆波兰表达式求值

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)$ ，其中 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;
}