实验五 基于二叉树的表达式求值算法_基于二叉树的表达式求值描述:输入一个表达式(表达式中的数均为小于10的正整数

实验五 基于二叉树的表达式求值
一、实验目的
1.掌握二叉树的二叉链表存储表示和二叉树的遍历等基本算法。
2.掌握根据中缀表达式创建表达式树的算法。
3.掌握基于表达式树的表达式求值算法。
二、实验内容
问题描述
输入一个表达式(表达式中的数均为小于 10 的正整数)，利用二叉树来表示该
表达式，创建表达式树，然后利用二叉树的遍历操作求表达式的值。
三、实验实习设备及开发环境
Visual studio 2022
四．实验实习过程步骤（注意是主要关键步骤，不是所有步骤，适当文字+截图说明）
Fucntion1：建立一个存放运算符的运算符栈和一个存放操作数的树栈。并且写出一系列有关栈操作的函数。因为这里是一个字符栈，一个树栈，所以很多功能都需要写两个函数。

Function2：比较运算符的优先级的函数，通过建一个二维数组，然后通过对应运算符的下标，然后找到对应优先级。

Function3：对表达式进行计算。

Function4：二叉树的创建函数。首先创建操作符栈OPRT，然后初始化。然后创建一个树栈存放子树OPND。然后将’=’压入OPRT来结束运算。然后读取字符串，当读入的是数字的时候，我们将创建一个子树，将数字作为data存储在子树中，然后压入栈中（这里因为读取的是字符串，很可能读取的是多位的数字，所以我们需要将数字合并）。如果读取到的是运算符，我们将比较运算符栈的栈顶元素和这个元素的优先级，如果是栈顶元素大于字符串中的运算符，那么我们就开始进行运算，将栈顶元素弹出，同时弹出两个操作数的子树，然后将他们合并成为一棵树，然后压入操作数栈中。如果是小于，则直接压入运算符数栈中，读取下一位。如果是等于就弹出运算符栈中的栈顶元素，然后读取下一位。

Function5：树的计算函数，利用递归进行运算。

Function6：主函数先建立一个操作数栈指针，然后指向最后得到的操作数栈。取这个操作数栈的栈顶元素，然后进行树的计算，得到结果。

五、实验实习结果及分析
试验成功，但是当我进行这种计算的时候计算的结果就不正确了。我觉得是优先级的问题，然后加了括号，但是结果还是-5，目前没找到问题所在。解决了，是在减法的时候，减数和被减数的顺序不对。

六．实验遇到的问题及解决办法，实验心得体会及对此实验的意见或建议（有就写，无可不写）。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 1000

char Precede[7][7] = { {'>','>','<','<','<','>','>'},
	{'>','>','<','<','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'<','<','<','<','<','=','0'},
	{'>','>','>','>','0','>','>'},
	{'<','<','<','<','<','0','='} };

typedef struct tree
{
	int data;
	struct tree* lchild, * rchild;
}BitNode, * Bittree;

typedef struct stack
{
	int* base;
	int* top;
	int stacksize;
}SqStack1;//运算符栈

typedef struct stack2
{
	Bittree* base;
	Bittree* top;
	int stacksize;
}SqStack2;//节点树栈

void InitStack1(SqStack1* S)
{
	S->base = calloc(MAX, sizeof(int));
	if (!S->base)
	{
		printf("内存分配失败\n");
		exit(0);
	}
	S->top = S->base;
	S->stacksize = MAX;
}

void InitStack2(SqStack2* S)
{
	S->base = calloc(MAX, sizeof(Bittree));
	if (!S->base)
	{
		printf("内存分配失败\n");
		exit(0);
	}
	S->top = S->base;
	S->stacksize = MAX;

}

void Push1(SqStack1* S, int ch)
{
	if (S->top - S->base == S->stacksize)
	{
		printf("栈满了\n");
		exit(0);
	}
	*S->top++ = ch;
}

void Push2(SqStack2* S, Bittree tree)
{
	if (S->top - S->base == S->stacksize)
	{
		printf("栈满了\n");
		exit(0);
	}
	*S->top++ = tree;
}

int Pop1(SqStack1* S)
{
	int result;
	if (S->base == S->top)
	{
		printf("栈空\n");
		exit(0);
	}
	result = *--S->top;
	return result;
}

Bittree Pop2(SqStack2* S)
{
	Bittree result;
	if (S->base == S->top)
	{
		printf("栈空\n");
		exit(0);
	}
	result = *--S->top;
	return result;
}

Bittree Gettop1(SqStack1* S)
{
	return *(S->top - 1);
}
Bittree Gettop2(SqStack2* S)
{
	return *(S->top - 1);
}

int sub(char ch)
{
	switch (ch)
	{
	case '+':
		return 0;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 3;
	case '(':
		return 4;
	case ')':
		return 5;
	case '=':
		return 6;
	}
}

char Getpre(char ch1, char ch2)
{
	return Precede[sub(ch1)][sub(ch2)];
}

int operate(int x1, int x2, int theta)
{
	switch (theta)
	{
	case '+':
		return x1 + x2;
	case '-':
		return x1 - x2;
	case '*':
		return x2 * x1;
	case '/':
		return x1/ x2;

	}
}

Bittree createtreenode( BitNode* a, BitNode* b, int data)
{
	Bittree tree = malloc(sizeof(BitNode));
	tree->data = data;
	tree->lchild = a;
	tree->rchild = b;
	return tree;
}

int StackEmpty1(SqStack1* s)
{
	if (s ->top==s->base)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
SqStack2* CreateTree(char* str)
{
	SqStack1* OPRT;//操作符栈
	OPRT = malloc(sizeof(SqStack1));
	SqStack2* OPND;
	OPND = malloc(sizeof(SqStack2));
	InitStack1(OPRT);
	InitStack2(OPND);
	Push1(OPRT, '=');
	int length = strlen(str);
	int i = 0;
	int theta;

	while ((str[i] != '\0' || Gettop1(OPRT) != '=')&&StackEmpty1(OPRT)==0)
	{
		if (str[i] >= '0' && str[i] <= '9')
		{
			int x1 = 0;
			while (str[i] >= '0' && str[i] <= '9')
			{
				x1 = x1 * 10 + str[i] - '0';
				i++;
			}
			Bittree tree1 = createtreenode(NULL, NULL, x1);
			Push2(OPND, tree1);
		}
		else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')' || str[i] == '=')
		{
			switch (Getpre(Gettop1(OPRT), str[i]))
			{
			case'>':
				theta = Pop1(OPRT);
				Bittree a, b;
				b = Pop2(OPND);
				a = Pop2(OPND);
				Bittree t;
				t=createtreenode(a, b, theta);
				Push2(OPND, t);
				break;
			case '=':
				Pop1(OPRT);
				i++;
				break;
			case '<':
				Push1(OPRT, str[i]);
				i++;
				break;
			}
		}
		else
		{
			printf("输入非法\n");
			exit(0);
		}
	}
	return OPND;
}

int caculate(Bittree tree)
{
	int lchild = 0, rchild = 0;
	if (tree == NULL)
	{
		printf("Invalid expression\n");
		exit(0);
	}
	if (tree->lchild== NULL && tree->rchild == NULL)
	{
		return tree->data;
	}
	else
	{
		lchild = caculate(tree->lchild);
		rchild = caculate(tree->rchild);
		return operate(lchild, rchild, tree->data);
	}
}
int main()
{
	char str[MAX];
	
	while (gets(str)&&strcmp(str,"=")!=0)
	{
		SqStack2* OPND = NULL;
		OPND = CreateTree(str);
		Bittree tree =NULL;
		tree = Gettop2(OPND);
		int result;
		result = caculate(tree);
		printf("计算结果是\n");
		printf("%d\n", result);
	}
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268