没事做写个有理数计算
前段时间看SICP比较有感觉，也把书上的一些作业实现了一遍。今天不明觉厉突然想用C实现一个计算有理数算式的程序，也算是增强一下自己对代码对程序的控制能力。程序的目的是计算形如 1|2*(3+3|4)这样的表达式，程序里为了区分除号和分数线，分数线用 | 表示。
为了增加程序可读性和模块性，没有在一个文件里实现所有功能模块，整个程序分成了几个部分：
1、字符串分析部分
2、常用例程部分
3、求值部分
其实这个程序就是一个小型的解释器，所有代码加起来大概600行左右。 字符串分析也就是一个词法扫描器，把 输入的字符串 转化成一个一个的节点，节点内容可能是 一个有理数，比如 1|2，可能是一个运算符，比如+ - 等，或者是一个括号，所以就把这个节点定义为以下数据结构：
typedef enum{
PARENTHESE,OPERATOR,RAT
}obj_type;
typedef struct obj{
obj_type type;
union{
struct{
char value;
}ch; //运算符和括号类型
struct{
int numer;
int denom;
}rat; // 有理数类型，包括分子分母
}data;
}obj; 词法扫描部分用了一点自动机理论，毕竟在字符串扫描方面，正则表达式和自动机理论是最有力的武器。词法扫描代码有大概150行左右，就不贴上来了，下面附件有整个代码的下载，总之呢，词法分析生成一个链表，链表的节点就是算术表达式的每一个单词元素。
现在有了表达式的抽象表达而不是字符串，我们就可以考虑对其进行求值了，我大概只能想出两种办法，一种是转化为后缀表达式然后通过栈求值；还有就是生成语法树，然后遍历语法树得到结果。思考再三还是采用了大家都了解的逆波兰表达式求值，毕竟鱼哥专门在数据结构里面讲过这个。
求值过称不复杂，只需要维持两个栈，一个用来存储操作数，一个存储操作符和括号。 具体步骤如下：
1、遍历链表的每个节点
2、若节点为有理数，则压入操作数栈rat_stack
3、若不为有理数，则需进行判断，若为+ 或 -，只要当前栈顶不是前括号，则弹出两个操作数和一个操作符进行运算，结果压入操作数栈。
然后再将读取到的操作符压入操作符栈
4、若为 * 或 /，则判断栈顶，若为 * /则如步骤3做一次运算，再将本运算符压栈。
5、（ 直接压栈
6、若为后括号，则一直重复步骤3中的运算过程，知道栈顶为前括号，然后扔掉前括号
7，最后检查操作符栈是否为空，不为空则重复步骤三运算步骤知道为空
最后操作数栈顶即为结果。。
最后一个模块是有理数四则运算，举一例足矣：
obj * rat_add(obj * arg1,obj *arg2)
{
int n1,n2,d1,d2,n,d;
obj * result = (obj *)malloc(sizeof(obj));
/* n1,n2,d1,d2分别为第一个和第二个参加运算的有理数对象的分子和分母*/
n1 = get_numer(arg1);
n2 = get_numer(arg2);
d1 = get_denom(arg1);
d2 = get_denom(arg2);
result->type = RAT;
n = n1*d2+n2*d1;
d = d1*d2;
set_numer(result,n/gcd(n,d)); //约分
set_denom(result,d/gcd(n,d));
return result;
}
最后贴上主函数：
int main()
{
char exp;
printf("输入表达式:\n>");
get_exp(exp);
print(cal(parse(exp)));
return 0;
}
水平很菜，发帖完全是为了 巩固自己所学的知识。SICP书中有句话讲得很好：计算机程序是写给人看的，而恰好能被计算机执行。这跟当时这本书出版的时代的主流论点完全相反，但是今天的时代证明这句话是对的。程序的可读性已经超过了效率的重要性。因为计算机硬件越来越快，所以牺牲可读性换取那一点效率是不明智的。从这本书中，我学到很多，他告诉我软件的本质就是抽象，就是模拟。
不管怎么说，这个帖子也算编辑完了，写得好坏也变得不那么重要了，重要的是通过一个一个的抽象系统的设计，编程水平正在快速的提高
页:
[1]