通过二叉树实现简易的计算机功能
程序大体分为三个步骤
1.将输入的中缀表达式转换为后缀表达式
2.将后缀表达式的各个元素放入二叉树
3.通过递归二叉树计算表达式的值
中缀表达式符号具有优先级且有括号转换成二叉树难度较大,所以这里首先转换成后缀表达式更有利于二叉树的实现
我们把表达式中的每个数字和操作符作为一个元素,因为操作符是字符型,数字是整型所以这里定义一个结构体用来存储元素
复制代码
1
2
3
4
5struct element{ int i = 0; char c; };
再定义一个结构体用来存放元素的数组,每个元素存储在这个数组中通过遍历即为表达式
复制代码
1
2
3
4
5struct earray{ element* e; int index;//数组长度 };
以下是栈的定义,用来后续对元素的操作
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23struct stack{ char n[maxsize]; int rear; }; stack* init(){ stack* s = new stack; s->rear = -1; return s; } insert(stack* s,char c){ if(s->rear < maxsize - 1){ s->n[s->rear+1] = c; s->rear++; }else{ cout << "栈满了" <<endl; } } delete1(stack* s){ if(s->rear > -1){ s->rear--; } }
获得后缀表达式
复制代码
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
64element e[maxsize];//因为局部指针函数使用完会销毁,所以这里使用全局变量 earray tran(stack* s,string str){ int num = 0; int index = 0;//e数组的下标 for(int i = 0; i < str.length(); i++){ // if(str[i] >= '0' && str[i] <= '9'){ num *= 10; num = num + str[i]-48; }else{ if(num!=0) { element Element; Element.i = num; e[index++] = Element; } num = 0; if(s->rear == -1 ||str[i] == '('){ insert(s,str[i]); }else if(str[i] == '+' || str[i] == '-'){ while(s->n[s->rear] == '+' || s->n[s->rear] == '-'|| s->n[s->rear] == '*'|| s->n[s->rear] == '/'){ element Element; Element.c = s->n[s->rear]; e[index++] = Element; delete1(s); } insert(s,str[i]); }else if(str[i] == '*' || str[i] == '/'){ if(s->n[s->rear] == '*' || s->n[s->rear] == '/'){ element Element; Element.c = s->n[s->rear]; e[index++] = Element; delete1(s); } insert(s,str[i]); }else if(str[i] == ')'){ while(s->n[s->rear] != '('){ element Element; Element.c = s->n[s->rear]; e[index++] = Element; delete1(s); } delete1(s); } } } if(str[str.length()-1] != ')'){ element Element; Element.i = num; e[index++] = Element; } while(s->rear != -1){ element Element; Element.c = s->n[s->rear]; e[index++] = Element; delete1(s); } earray ea; ea.e = e; ea.index = index; return ea; }
将后缀表达式转换为二叉树
定义了一个存放树节点的栈
复制代码
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//树的结点 struct node{ element ele; node* lchild = NULL; node* rchild = NULL; }; //栈 struct tstack{ node* e[maxsize]; int rear; }; tstack* tinit(){ tstack* s = new tstack; s->rear = -1; return s; } insert(tstack* s,node* e){ if(s->rear < maxsize - 1){ s->rear++; s->e[s->rear] = e; }else{ cout << "栈满了" <<endl; } } node* delete1(tstack* s){ if(s->rear > -1){ s->rear--; } return s->e[s->rear + 1]; }
后缀表达式有一个规律就是表达式开头都为两个数字结尾为操作符
如:中缀:1+2 * 3 + 4 后缀:1 2 3 * + 4 +
如果树节点的元素是数字则压入树节点栈
如果树节点的元素是操作符则将栈顶两个元素删除并作为该节点的左孩子和右孩子存入栈中
最后返回的就是树的根节点
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19node* tree(earray ea,tstack* ts){ for(int j = 0; j < ea.index;j++){ if(ea.e[j].i != 0){//这个元素是个数字 node* n = new node; n->ele = ea.e[j]; insert(ts,n); }else{ node* node1 = delete1(ts); node* node2 = delete1(ts); node* node3 = new node; node3->ele = ea.e[j]; node3->lchild = node1; node3->rchild = node2; insert(ts,node3); } } return ts->e[0]; }
递归遍历二叉树计算表达式的值
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20int cal(node* n){ int sum = 0; if(n->ele.c == '+'){ sum = cal(n->lchild) + cal(n->rchild); } if(n->ele.c == '-'){ sum = cal(n->lchild) - cal(n->rchild); } if(n->ele.c == '*'){ sum = cal(n->lchild) * cal(n->rchild); } if(n->ele.c == '/'){ sum = cal(n->lchild) / cal(n->rchild); } if(n->ele.i != 0){ return n->ele.i; } return sum; }
主函数
复制代码
1
2
3
4
5
6
7
8
9
10int main(){ stack* symbol = init(); earray ea = tran(symbol,"(1+2)*3+4"); tstack* ts = tinit(); node* n = tree(ea,ts); cout << cal(n); return 0; }
最后
以上就是帅气芹菜最近收集整理的关于通过二叉树实现简易的计算机功能的全部内容,更多相关通过二叉树实现简易内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复