MyLisp项目日志：波兰表达式计算与错误处理

项目
2.7k words

波兰表达式计算

AST树的结构

在上一篇我们已经可以读取分析波兰表达式的内部结构了，这一篇我们将会对表达式进行计算，得到计算的结果

之前有提到过抽象语法树，AST，他是用来表示用户输入的的表达式的结构的，操作数和操作符这些需要被处理的数据都存在叶子节点上，而非叶子节点上存储的是遍历和求值的信息

在这里需要看一下mpc_ast_t的内部结构

1
2
3
4
5
6
7
typedef struct mpc_ast_t {
  char* tag;
  char* contents;
  mpc_state_t state;
  int children_num;
  struct mpc_ast_t** children;
} mpc_ast_t;

  • tag表示节点内容之前的标签，他表示解析这个节点用到的规则，例如expr|number|regex

  • contents包含了节点的具体内容，例如add、(，对于非叶子节点，这个内容为空

  • state表示这个节点所处的状态，例如行数和列数，这里不会用到

  • 最后两个成员就是表示树的结构了，这里为了支持多叉树，采用指针数组的方式记录

运算符与数字的转换

在我们进行求值之前，我们需要遍历上面的AST，然后对于每一个叶子节点，想办法提取出他们的共同特征，以此分辨他们的功能

1
2
3
4
5
6
7
8
9
10
11
12
MyLisp> * 10 (+ 1 51)
>
  regex
  operator|char:1:1 '*'
  expr|number|regex:1:3 '10'
  expr|>
    char:1:6 '('
    operator|char:1:7 '+'
    expr|number|regex:1:9 '1'
    expr|number|regex:1:11 '51'
    char:1:13 ')'
  regex
  • tag有number的一定是数字
  • expr没有number的第一个字符是左括号，第二个一定是操作符

因为tag和contents都是字符串，因此我们可以使用一些辅助函数

函数名 作用
atof 将 char* 转化为 double 型
strcmp 接受两个 char* 参数，比较他们是否相等，如果相等就返回 0
strstr 接受两个 char*，如果第一个字符串包含第二个，返回其在第一个中首次出现的位置的指针，否则返回 0

这样就可以写出递归求值的函数了

基本思路如下

  1. 如果当前节点有number，则转换为数字并返回
  2. 处理操作符和操作数
    1. 操作符是当前节点的第二个孩子，存储到op中
    2. 操作数是第三个孩子的内容，但是这个操作数仍有可能是一个表达式，因此进入递归，返回值则是子表达式的结果
  3. 处理表达式
    1. 迭代当前节点的剩余子节点（如果有），也就是处理子表达式
    2. 对于每个子表达式都具体计算
  4. 返回得到的结果

写成代码就是下面这个样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double eval(mpc_ast_t* t) {
	// 如果是数字，直接转换返回
	if (strstr(t->tag, "number")) {
		return atof(t->contents);
	}

	// 取操作符
	char* op = t->children[1]->contents;

	// 进入子表达式，如果是数字直接返回数字，如果是表达式则计算子表达式，记录返回的结果到x
	long x = eval(t->children[2]);

	// 计算其他的子表达式并且合并结果到x
	int i = 3;
	while (strstr(t->children[i]->tag, "expr")) {
		x = eval_op(x, op, eval(t->children[i]));
		i++;
	}

	return x;
}

这其中计算函数eval_op如下，这里只写一下加减乘除，最终代码会补全

1
2
3
4
5
6
7
double eval_op(double x, char* op, double y) {
  if (strcmp(op, "+") == 0) { return x + y; }
  if (strcmp(op, "-") == 0) { return x - y; }
  if (strcmp(op, "*") == 0) { return x * y; }
  if (strcmp(op, "/") == 0) { return x / y; }
  return 0;
}

最后我们只需要将输出的结果打印即可

1
2
3
double result = eval(r.output);
printf("%g\n", result);
mpc_ast_delete(r.output);

异常处理

对于数学计算来说，有一些特殊的处理，例如除数不为0，模的数不为0，当我们直接输入就会出错，但是不同编译器的处理不同，甚至有的会直接崩溃

我们不能这么粗暴，给用户一点错误提示就好

C语言可以设计很多的错误处理的方式，这里我们采用一种使错误也成为表达式求值的结果

简单说就是表达式求值的结果要么是数字，要么是错误

MyLisp Value的封装

为例达到上面的目的，我们将类型（数字或者错误），具体的数值，具体的错误封装成一个结构体，命名为MLval，意为MyLisp val

定义如下

1
2
3
4
5
6
typedef struct
{
	int type;
    double num;
    int err;
}MLval;

枚举处理

我们可以让type等于0的时候，让结构体表示一个数字，等于1的时候，让结构体表示一个错误

当我们使用枚举的时候，就提高了代码的可读性

定义如下

1
2
3
4
5
6
7
8
9
10
11
12
enum err
{
	MLERR_DIV_ZERO, // 除0
	MLERR_BAD_OP, // 非法操作符
	MLERR_BAD_NUM // 非法数字
};

enum type
{
	MLVAL_NUM, // 表示数字
	MLVAL_ERR // 表示错误
};

初始化

结构体和枚举都有了，接下来就是初始化，将数值转化为结构体对象，将错误转化为结构体对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MLval MLval_num(double x)
{
	MLval v;
	v.type = MLVAL_NUM; // 类型赋值
	v.num = x; // 数字赋值
	return v;
}

MLval MLval_err(int x)
{
	MLval v;
	v.type = MLVAL_ERR; // 类型赋值
	v.err = x; // 错误赋值
	return v;
}

打印

因为MLval不是一个简单的数字，而是结构体，因此我们就需要重新写一个打印函数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MLval_print(MLval v)
{
	switch (v.type)
	{
	case MLVAL_NUM:printf("%g", v.num); break; // 如果是数字，直接打印
	case MLVAL_ERR: // 如果是错误，区分错误类型后报错
		if (v.err == MLERR_DIV_ZERO)
			printf("Error: Division By Zero!\n");
		if (v.err == MLERR_BAD_OP)
			printf("Error: Invalid Operator!\n");
		if (v.err == MLERR_BAD_NUM)
			printf("Error: Invalid Number!");
		break;
	}
}

求值

因为我们将数字封装了，所以求值函数也需要改动，同时加入错误的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MLval eval_op(MLval x, char* op, MLval y)
{
    // 如果是错误类型，直接返回
	if (x.type == MLVAL_ERR) { return x; }
	if (y.type == MLVAL_ERR) { return y; }

    // 加减乘除取模乘方取最大最小值
	if (strcmp(op, "+") == 0 || strcmp(op, "add") == 0) { return MLval_num(x.num + y.num); }
	if (strcmp(op, "-") == 0 || strcmp(op, "sub") == 0) { return MLval_num(x.num - y.num); }
	if (strcmp(op, "*") == 0 || strcmp(op, "mul") == 0) { return MLval_num(x.num * y.num); }
	if (strcmp(op, "/") == 0 || strcmp(op, "div") == 0) 
    {
		return y.num == 0 ? MLval_err(MLERR_DIV_ZERO) : MLval_num(x.num / y.num);
	}
	if (strcmp(op, "%") == 0 || strcmp(op, "mod")==0) 
    {
		return y.num == 0 ? MLval_err(MLERR_DIV_ZERO) : MLval_num(fmod(x.num, y.num));
	}
	if (strcmp(op, "^") == 0) { return MLval_num(pow(x.num, y.num)); }
	if (strcmp(op, "min") == 0) { return MLval_num((x.num < y.num) ? x.num : y.num); }
	if (strcmp(op, "max") == 0) { return MLval_num((x.num > y.num) ? x.num : y.num); }

	return MLval_err(MLERR_BAD_OP);
}

除此之外，计算函数也需要修改一下，而且strtof函数可以通过检测errno变量查看是否转换成功

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
MLval eval(mpc_ast_t* t)
{
    // 如果是数字则进行转换
	if (strstr(t->tag, "number"))
	{
		char* endptr;
		double num = strtod(t->contents, &endptr);
		// 判断是否转换成功
        if (*endptr != '\0') 
        {
			return MLval_err(MLERR_BAD_NUM);
		}
		return MLval_num(num);
	}

	char* op = t->children[1]->contents;

	MLval x = eval(t->children[2]);

	int i = 3;
	while (strstr(t->children[i]->tag, "expr"))
	{
		MLval y = eval(t->children[i]);
		x = eval_op(x, op, y);
		i++;
	}
	return x;
}

最后直接进行输出就行

v0.1.1

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
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h> 
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include"mpc.h"
void PrintPrompt()
{
	printf("MyLisp Version 0.1.1\n");
	printf("By jasmine-leaf\n");
	printf("Press Ctrl+c to Exit\n\n\n");
}
// v0.0.1
// 实现了用户输入和读取功能
// v0.0.2
// 增加了波兰表达式的解析功能
// v0.1.0
// 增加了波兰表达式的求值功能
// 增加了min、max、乘方运算
// v0.1.1
// 增加了运算报错

#ifdef _WIN32 

// 为实现跨平台功能
// 在windows平台下定义实现editline和history的同名函数

#define INPUT_MAX 2048 // 缓冲区最大值

static char Buffer[INPUT_MAX]; // Buffer输入缓冲区


char* readline(char* prompt) // 模拟实现readline
{
	fputs(prompt, stdout);
	fgets(Buffer, INPUT_MAX, stdin);


	char* tmp = malloc(strlen(Buffer) + 1);
	if (tmp != NULL)
	{
		strcpy(tmp, Buffer);
		tmp[strlen(tmp) - 1] = '\0';
	}
	return tmp;
}

void add_history(char* unused)
{}

#else
#ifdef __linux__ // 在linux平台下
#include<editline/readline.h>
#include<editline.history.h>
#endif

#ifdef __MACH__ // 在mac平台下
#include<editline/readline.h>
#endif
#endif 

enum err
{
	MLERR_DIV_ZERO, // 除0
	MLERR_BAD_OP, // 非法操作符
	MLERR_BAD_NUM // 非法数字
};

enum type
{
	MLVAL_NUM, // 表示数字
	MLVAL_ERR // 表示错误
};

typedef struct 
{
	int type;
	double num;
	int err;
}MLval;

MLval MLval_num(double x)
{
	MLval v;
	v.type = MLVAL_NUM; // 类型赋值
	v.num = x; // 数字赋值
	return v;
}

MLval MLval_err(int x)
{
	MLval v;
	v.type = MLVAL_ERR; // 类型赋值
	v.err = x; // 错误赋值
	return v;
}

// 打印结果
void MLval_print(MLval v)
{
	switch (v.type)
	{
	case MLVAL_NUM:printf("%g", v.num); break; // 如果是数字，直接打印
	case MLVAL_ERR: // 如果是错误，区分错误类型后报错
		if (v.err == MLERR_DIV_ZERO)
			printf("Error: Division By Zero!\n");
		if (v.err == MLERR_BAD_OP)
			printf("Error: Invalid Operator!\n");
		if (v.err == MLERR_BAD_NUM)
			printf("Error: Invalid Number!");
		break;
	}
}

 // 解析并计算操作符
MLval eval_op(MLval x, char* op, MLval y)
{
	// 如果是错误类型，直接返回
	if (x.type == MLVAL_ERR) { return x; }
	if (y.type == MLVAL_ERR) { return y; }

	// 加减乘除取模乘方取最大最小值
	if (strcmp(op, "+") == 0 || strcmp(op, "add") == 0) { return MLval_num(x.num + y.num); }
	if (strcmp(op, "-") == 0 || strcmp(op, "sub") == 0) { return MLval_num(x.num - y.num); }
	if (strcmp(op, "*") == 0 || strcmp(op, "mul") == 0) { return MLval_num(x.num * y.num); }
	if (strcmp(op, "/") == 0 || strcmp(op, "div") == 0)
	{
		return y.num == 0 ? MLval_err(MLERR_DIV_ZERO) : MLval_num(x.num / y.num);
	}
	if (strcmp(op, "%") == 0 || strcmp(op, "mod") == 0)
	{
		return y.num == 0 ? MLval_err(MLERR_DIV_ZERO) : MLval_num(fmod(x.num, y.num));
	}
	if (strcmp(op, "^") == 0) { return MLval_num(pow(x.num, y.num)); }
	if (strcmp(op, "min") == 0) { return MLval_num((x.num < y.num) ? x.num : y.num); }
	if (strcmp(op, "max") == 0) { return MLval_num((x.num > y.num) ? x.num : y.num); }

	return MLval_err(MLERR_BAD_OP);
}

// 递归计算
MLval eval(mpc_ast_t* t)
{
	// 如果是数字则进行转换
	if (strstr(t->tag, "number"))
	{
		char* endptr;
		double num = strtod(t->contents, &endptr);
		// 判断是否转换成功
		if (*endptr != '\0')
		{
			return MLval_err(MLERR_BAD_NUM);
		}
		return MLval_num(num);
	}

	char* op = t->children[1]->contents;

	MLval x = eval(t->children[2]);

	int i = 3;
	while (strstr(t->children[i]->tag, "expr"))
	{
		MLval y = eval(t->children[i]);
		x = eval_op(x, op, y);
		i++;
	}
	return x;
}

void Lisp()
{
	// 创建解析器
	mpc_parser_t* Number = mpc_new("number");
	mpc_parser_t* Operator = mpc_new("operator");
	mpc_parser_t* Expr = mpc_new("expr");
	mpc_parser_t* MyLisp = mpc_new("mylisp");

	// 定义
	mpca_lang(MPCA_LANG_DEFAULT,
		"                                                                                \
		 number   : /-?[0-9]+(\\.[0-9]*)?/ ;                                             \
		 operator : '+' | '-' | '*' | '/' | '%' | '^' | /add|sub|mul|div|min|max|mod/ ;  \
		 expr     : <number> | '(' <operator> <expr>+ ')' ;                              \
		 lispy    : /^/ <operator> <expr>+ /$/ ;                                         \
		",
		Number, Operator, Expr, MyLisp);

	while (1)
	{
		char* input = readline("MyLisp> ");
		add_history(input);

		// 尝试分析用户输入
		mpc_result_t r;
		if (mpc_parse("<stdin>", input, MyLisp, &r))
		{
			MLval result = eval(r.output);
			MLval_print(result);
			putchar('\n');
			mpc_ast_delete(r.output);
		}
		else
		{
			// 其他打印失败的情况
			mpc_err_print(r.error);
			mpc_err_delete(r.error);
		}

		free(input); // 释放在readline中malloc的空间
	}

	mpc_cleanup(4, Number, Operator, Expr, MyLisp);
}

int main()
{
	PrintPrompt();
	Lisp();
	return 0;
}


os

其实是有尝试将中缀表达式转化为前缀表达式的，就可以实现正常的顺序输入计算，达到python的那种计算手感，但是遇到一些问题

如果直接使用栈将中缀转化为前缀，以字符串的方式逐个转化，会遇到空格无法正常转换的问题，而空格非常重要，例如1 2 和12就是两个数字和一个数字的区别，其次是负数的问题，例如 -1和 - 1的问题，既可以解释成负1也可以解释成减1

为此我想有两个解决方案，一是继续尝试利用栈转化，修修补补，二是重新写一个解析器，就是相当于重新设计了一门语言（？），只需要利用输入方案的区别判断是中缀还是前缀

可能会在完成各项基本功能后修修补补逐渐完成，之后也会出C++版本的，如果笔者能力足够的话，会期望为mpc库提供issue，或者写成一个自己的库，使之变成更适配C++的版本

Comments