问题我就不描述了
二叉树我也不累述了
回顾一下中缀表达式转换二叉树的过程 同时结合 二叉树的是自底向上计算的性质，我们能得到什么呢
即 ：优先计算的表达式在二叉树的底部，换句话说权值越高，其在二叉树的位置就越低，即 自底向上计算的时候也就越先运算。
但是 对于递归栈来说，是自顶向下生成的
也就是说，在生成表达式二叉树的时候，我们是先找到这个表达式里的权值最小的那个操作符，然后递归的得到左右子树的值的，然后运算的。
那么按照这个思想，我们来搭建一下大体的框架
double tryCalc(char * str, int l, int r) {
int pos = -1;
//扫描一遍找到最小权值的pos
for (int i = l; i < r; i++) {
}
}
//递归计算表达式
// pos == -1 即 说明是个数字
if (pos == -1) {
}
//递归计算 权值最小的操作符的 左子树 和 右子树的值
else {
double a = tryCalc(str, l, pos );
double b = tryCalc(str, pos + 1, r);
switch (str[pos]) {
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
case'^':return pow(a, b);
}
}
}
那么框架就这么搭建完了，很好理解应该
接下来就是 每个自框架下的具体实现了
-
扫描得到表达式的最小权值的位置
int pos = -1;
//扫描一遍找到最小权值的pos
for (int i = l; i < r; i++) {
}
首先我们要定义一下依据优先算的操作优先级高的性质定义表达式权限规则
空的权值 为 INF
数字的权值为 INF - 1
‘+’“-” 的权值 为表达式的基准权值 + 1
这里引入了基准权值 为什么呢
因为考虑到 （）的情形 ：
当出现 （ 的时候 整个表达式的基准权值就升高了
出现 ） 的时候 整个表达式的基准权值就下降了
“*，/ ,^” 等之类的权值就分别 + 2 ， + 2 ， +3
所以 代码如下表示
int pos = -1, cur_pri = INF - 1, temp_pri = 0;
for (int i = l; i < r; i++) {
int now_pri = INF;
switch (str[i]) {
case '(': temp_pri += 100; break;
case ')': temp_pri -= 100; break;
case '=': now_pri = 0 + temp_pri; break;
case '+':
case '-': now_pri = 1 + temp_pri; break;
case '*':
case '/': now_pri = 2 + temp_pri; break;
case '^': now_pri = 3 + temp_pri; break;
}
if (cur_pri >= now_pri) {
pos = i;
cur_pri = now_pri;
}
}
ok 完成了一个段落的细节了
接下来 完成 下一个方面
2. 递归计算表达式:
a) 数字的计算
b) 数字和操作符结合的计算
** 数字的计算**
很简单的处理一下 去掉前导空格 然后 用 atof转换成double值就好
if (pos == -1) {
//去掉前导的空格
while (l <= r &&( str[l] > '9' || str[l] < '0')) l++;
//将 str 里的 l 到 r转换为数字
double num = atof(str + l);
return num;
}
至于 数字和操作符结合的计算，我们已经实现了
自此 我们就完成了 超级简单的递归栈的实现
#define INF 0x3f3f3f3f // 宏定义一下 最大值 INF
double tryCalc(char * str, int l, int r) {
int pos = -1;
int tempPri = 0;//代表表达式的基准权值 如果有( ) 那么括号内的权值也会相应的上升下降
int curPri = INF - 1;//当前权值小一些 代表数字的权值 INF 为 null的权值
//扫描一遍找到最小权值的pos
for (int i = l; i < r; i++) {
int nowPri = INF;
switch (str[i]){
case'(':tempPri += 100; break;
case')':tempPri -= 100; break;
case'-':
case'+':nowPri = tempPri + 1; break;
case '*':
case'/':nowPri = tempPri + 2; break;
case '^':nowPri = tempPri + 3; break;
}
if (curPri >= nowPri) {
pos = i;
curPri = nowPri;
}
}
//递归计算表达式
// pos == -1 即 说明是个数字
if (pos == -1) {
//去掉前导的空格
while (l <= r &&( str[l] > '9' || str[l] < '0')) l++;
//将 str 里的 l 到 r转换为数字
double num = atof(str + l);
return num;
}
//递归计算 权值最小的操作符的 左子树 和 右子树的值
else {
double a = tryCalc(str, l, pos );
double b = tryCalc(str, pos + 1, r);
switch (str[pos]) {
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
case'^':return pow(a, b);
}
}
}
好 运行一下 应该是没有问题的
接下来会扩展一下表达式求值 ，我们会引入 变量 从而可以计算自定义的公式的值
类似 于
x = 1
y = 2
求 2*x + y 值为多少
看一下大致上的效果
2 * x + y
please input x = 2
please input y = 1
test : 5.000000
x * x * x
please input x = 3
test : 27.000000
(x + y + z + i)/4
please input x = 2
please input y = 3
please input z = 4
please input i = 5
test : 3.500000
很 炫酷的效果
其实吧 我们分析一下 要实现这种效果需要什么呢
其实就是一个简单map
当扫描到 字符的时候 就从map里取一下相应的值并返回就好
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
map<char, double> value_map;
double tryCalc(char * str, int l, int r) {
int pos = -1;
int tempPri = 0;//代表表达式的基准权值 如果有( ) 那么括号内的权值也会相应的上升下降
int curPri = INF - 1;//当前权值小一些 代表数字的权值 INF 为 null的权值
//扫描一遍找到最小权值的pos
for (int i = l; i < r; i++) {
int nowPri = INF;
switch (str[i]){
case'(':tempPri += 100; break;
case')':tempPri -= 100; break;
// 赋值操作的权值最低 为 0;
case'=':nowPri = tempPri + 0; break;
case'-':
case'+':nowPri = tempPri + 1; break;
case '*':
case'/':nowPri = tempPri + 2; break;
case '^':nowPri = tempPri + 3; break;
}
if (curPri >= nowPri) {
pos = i;
curPri = nowPri;
}
}
//处理 = 运算
if (str[pos] == '=') {
//去掉前导空格
while (l < r && str[l] == ' ')++l;
double a = tryCalc(str, pos + 1, r);
value_map[str[l]] = a;
return a;
}
//递归计算表达式
// pos == -1 即 说明是个数字 或 变量名
if (pos == -1) {
for (int i = l; i < r; i++) {
if (str[i] < 'a' || str[i] > 'z') continue;
if (value_map.find(str[i]) == value_map.end()) {
char msg[100];
sprintf(msg, "There is no var named = %c", str[i]);
throw runtime_error(msg);
}
return value_map[str[i]];
}
//去掉前导的空格
while (l <= r &&( str[l] > '9' || str[l] < '0')) l++;
//将 str 里的 l 到 r转换为数字
double num = atof(str + l);
return num;
}
//递归计算 权值最小的操作符的 左子树 和 右子树的值
else {
double a = tryCalc(str, l, pos );
double b = tryCalc(str, pos + 1, r);
switch (str[pos]) {
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
case'^':return pow(a, b);
}
}
}
//解析表达式里的字符变量 填充map
void resolveXYZ(char * str, int l, int r) {
value_map.clear();
for (int i = 0; i < r; i++) {
if (str[i] >= 'a' && str[i] <= 'z'&&value_map.find(str[i]) == value_map.end()) {
double value;
printf("please input %c = ", str[i]);
scanf("%lf",&value);
value_map[str[i]] = value;
getchar();
}
}
}
int main() {
char str[1000];
while (scanf("%[^\n]s", str) != EOF) {
getchar();
//printf("%lf\n", calc(str, 0, strlen(str)));
resolveXYZ(str, 0, strlen(str));
printf("test : %lf\n",tryCalc(str,0,strlen(str)));
}
return 0;
}
好了 基本上就是这个样子啦 ，开心 。
京公网安备 11010502036488号