【算法作业】实验四：逆波兰表达式求值 & Fibonacci数列的尾递归与非递归程序

---

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

1.题目

掌握递归的基本语法和思想，利用递归程序实现逆波兰表达式，并分析算法复杂度。

2.问题分析与算法设计思路

这里实现了对多位数整的操作，运算仅包含四则运算。输入中使用.来将不同的操作数隔开，使用@表示表达式的结束。

使用栈的实现方法在另一篇博客中写过，请参考：计算后缀表达式-算法与数据结构-栈的运用-C++语言实现。这里我们将使用递归的方法来实现（虽然也用到了栈，但仅仅是为了从尾部开始读取字符而已）。

思路：
每个操作符将需要两个操作数，可以为表达式构建一颗递归树，每个操作数可能就是表达式中的一个数字，也可能要由一个子表达式（递归就来了）计算得到。

以输入3.5.2.-*7.+@为例，构建递归树：

注意：
由于我是从表达式的尾部开始读取字符，而减法、除法运算并不满足交换律，因此需要额外调整一下。

遇到问题：
再调试过程中遇到了一个很奇怪的问题，我现在仍没有弄清楚原理，我将它记录在问答社区：有个带函数的表达式前加负号无效。在下面的代码中，采用了避免该问题的写法。

3.算法实现

//逆波兰表达式——递归 
#include
#include
#include
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 "<
	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.*@
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

代码更新（9月19日）：

改变了函数nbl()中不同四则运算分支的代码写法，这样看起来更加简洁和明确，调试时查看中间结果也更加的方便。

//逆波兰表达式——递归 
#include
#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

4.运行结果

输出的t为每次四则运算得到的中间结果。

5.算法分析

算法的时间复杂度应为：$o(n)$，其中 n 为输入表达式的长度。

---

第二题：Fibonacci数列的尾递归与非递归程序

1.题目

将Fibonacci数列的递归求解方法转为尾递归求解；借助栈实现递归转非递归程序。

2.问题分析与算法设计思路

主要是学会可递归问题的多种写法。

3.算法实现

一、尾递归
关于使用尾递归，可以参考一下：尾递归实现斐波那契数

//斐波那契尾递归实现
#include
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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、使用栈的非递归

//斐波那契使用栈非递归实现 
#include
#include
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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

4.运行结果

5.算法分析

算法复杂度为：$o(n)$。

这里的递归写法时间开销要比非递归大一些（即使不考虑递归操作本身的原因），因为会存在重复计算。例如递归计算$f(5)$，则需要计算$f(4)$和$f(3)$，而计算$f(4)$中又计算了一次$f(3)$。这个问题据说可以用记忆化进行优化，但我还没有实操尝试过。

---

感谢阅读

博主主页：清风莫追

CSDN话题挑战赛第2期
参赛话题：学习笔记