没事做写个有理数计算

川本姨夫

      前段时间看SICP比较有感觉，也把书上的一些作业实现了一遍。今天不明觉厉突然想用C实现一个计算有理数算式的程序，也算是增强一下自己对代码对程序的控制能力。

     程序的目的是计算形如 1|2*(3+3|4)这样的表达式，程序里为了区分除号和分数线，分数线用 | 表示。

     为了增加程序可读性和模块性，没有在一个文件里实现所有功能模块，整个程序分成了几个部分：
        1、字符串分析部分
        2、常用例程部分
        3、求值部分

     其实这个程序就是一个小型的解释器，所有代码加起来大概600行左右。 字符串分析也就是一个词法扫描器，把 输入的字符串 转化成一个一个的节点，节点内容可能是 一个有理数，比如 1|2，可能是一个运算符，比如+ - 等，或者是一个括号，所以就把这个节点定义为以下数据结构：

1. typedef enum{
   
2.     PARENTHESE,OPERATOR,RAT
   
3. }obj_type;
   
4. 
   
5. typedef struct obj{
   
6.      obj_type type;
   
7.      union{
   
8.            struct{
   
9.                char value;
   
10.                      }ch;               //运算符和括号类型
    
11.            struct{
    
12.                 int numer;
    
13.                 int denom;
    
14.                      }rat;              // 有理数类型，包括分子分母
    
15.                 }data;
    
16. }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[1024];

        printf("输入表达式:\n>");
        get_exp(exp);
        print(cal(parse(exp)));

        return 0;
}


     水平很菜，发帖完全是为了 巩固自己所学的知识。SICP书中有句话讲得很好：计算机程序是写给人看的，而恰好能被计算机执行。这跟当时这本书出版的时代的主流论点完全相反，但是今天的时代证明这句话是对的。程序的可读性已经超过了效率的重要性。因为计算机硬件越来越快，所以牺牲可读性换取那一点效率是不明智的。从这本书中，我学到很多，他告诉我软件的本质就是抽象，就是模拟。
    不管怎么说，这个帖子也算编辑完了，写得好坏也变得不那么重要了，重要的是通过一个一个的抽象系统的设计，编程水平正在快速的提高
ratcal.rar (196.48 KB, 下载次数: 0)

2014-8-21 23:40 上传

点击文件名下载附件
VC环境