目录

1 利用栈和递归算法两种方式实现逆波兰表达式

代码：

运行截图：

​​​​​​​2 介绍递归算法思路，并以 8 9 2 + - 7 *为例说明算法的执行过程。

递归算法思路：

算法的执行过程：

递归算法的执行过程：

 利用栈非递归算法的执行过程：

​​​​​​​1 利用栈和递归算法两种方式实现逆波兰表达式

代码：

#include <iostream>#include <stack>using namespace std;/*逆波兰的递归函数*/int DBolan(char arr[], int& i) {if (arr[i] >= '0' && arr[i] <= '9') {return arr[i] - '0';}else {if (arr[i] == '+') {int x = DBolan(arr, --i);int y = DBolan(arr, --i);return y + x;}else if (arr[i] == '-') {int x = DBolan(arr, --i);int y = DBolan(arr, --i);return y - x;}else if (arr[i] == '*') {int x = DBolan(arr, --i);int y = DBolan(arr, --i);return y * x;}else if (arr[i] == '/') {int x = DBolan(arr, --i);int y = DBolan(arr, --i);return y / x;}}}/*利用栈来解决逆波兰*/int Bolan(char arr[], int n) {stack<int>my;for (int i = 0; i < n; ++i) {int tmp;if (arr[i] >= '0' && arr[i] <= '9') {my.push(arr[i] - '0');}else {if (arr[i] == '+') {int x = my.top();my.pop();int y = my.top();my.pop();tmp = y + x;my.push(tmp);}else if (arr[i] == '-') {int x = my.top();my.pop();int y = my.top();my.pop();tmp = y - x;my.push(tmp);}else if (arr[i] == '*') {int x = my.top();my.pop();int y = my.top();my.pop();tmp = y * x;my.push(tmp);}else {int x = my.top();my.pop();int y = my.top();my.pop();tmp = y / x;my.push(tmp);}}}return my.top();}int main() {char arr[] = { '8', '9', '2', '+', '-', '7', '*' };int num = 7;cout << "逆波兰非递归的结果：" << Bolan(arr, num) << endl;--num;cout << "逆波兰递归的结果：" << DBolan(arr, num) << endl;return 0;}

运行截图：

​​​​​​​2 介绍递归算法思路，并以 8 9 2 + - 7 *为例说明算法的执行过程。

递归算法思路：

逆波兰表达式就是将A op B变为A B op的形式，比如A+B变为A B +。所有的逆波兰表达式都是利用此方法不断嵌套。

算法的执行过程：

递归算法的执行过程：

 利用栈非递归算法的执行过程：