目录
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 +。所有的逆波兰表达式都是利用此方法不断嵌套。
算法的执行过程：
递归算法的执行过程：
利用栈非递归算法的执行过程：
