轻量级的面向对象 C 语言编程框架 LW_OOPC 介绍

下面，再举一个稍微复杂的例子，它的覆盖面是足够全面的，足以一瞥面向对象编程的3个要素：数据抽象、继承和多态。通过这个例子，我们期望展现出LW_OOPC在遭遇问题本身比较复杂的情形下，是如何从容应对的，以加深读者对LW_OOPC的认识。（备注：该问题来自《C++沉思录》第八章的例子，有兴趣的读者可以对照参阅）

问题描述：

​ 此程序涉及的内容是用来表示算术表达式的树。例如，表达式（-5）*（3+4）对应的树为：

​ 一个表达式树包括代表常数、一元运算符和二元运算符的节点。这样的树结构在编译器和计算器程序中都可能用到。

我们希望能通过调用合适的函数来创建这样的树，然后打印该树的完整括号化形式。例如，我们希望

#include "stdio.h"
#include "Expr.h"
 
int main(){
    
      
  Expr* expr1 = Expr_new();
  Expr* expr2 = Expr_new();
  Expr* expr3 = Expr_new();
  Expr* expr = Expr_new();

  expr1->initUnaryX(expr1, "-", 5);
  expr2->initBinaryX(expr2, "+", 3, 4);
  expr3->initBinary(expr3, "*", expr1, expr2);
  expr->initBinary(expr, "*", expr3, expr3);

  expr3->print(expr3);
  printf("\n");
  expr->print(expr);
  printf("\n");

  Expr_delete(expr);
  Expr_delete(expr3);
  Expr_delete(expr2);
  Expr_delete(expr1);

  return 0;
}

打印

((-5)*(3+4))

(((-5)*(3+4))*((-5)*(3+4)))

作为输出。此外，我们不想为这些表达式的表示形式操心，更不想关心有关它们内存分配和回收的事宜。

​ 这个程序所做的事情在很多需要处理复杂输入的大型程序中是很典型的，例如编译器、编辑器、CAD/CAM系统等。此类程序中通常要花费很大的精力来处理类似树、图和类似的数据结构。这些程序的开发者永远需要面对诸如内存分配、灵活性和效率之类的问题。面向对象技术可以把这些问题局部化，从而确保今后发生的一系列变化不会要求整个程序中的其他各个部分随之做相应调整。

解决方案：

​ 通过考查这个树结构，会发现这里有3种节点。一种表示整数表达式，包含一个整数值，无子节点。另外两个分别表示一元表达式和二元表达式，包含一个操作符，分别有一个或两个子节点。我们希望打印各种节点，但是具体方式需要视要打印节点的类型而定。这就是动态绑定的用武之地了：我们可以定义一个虚函数（print）来指明应当如何打印各种节点。动态绑定将会负责在运行时基于打印节点的实际类型调用正确的函数。

​ 首先，我们抽象出“节点”的概念，抽象类的名字定为Expr_node，它提供了打印的抽象接口，所有的实际节点类型均从它派生：

ABS_CLASS(Expr_node)
{
    
      
  void (*print)(Expr_node* t);
};

具体类的情形怎样？这些具体类型中最简单的一类是包含一个整数，没有子节点的节点：

CLASS(Int_node)
{
    
      
   EXTENDS(Expr_node);  // 继承Expr_node抽象类
   int n;      
   void (*init)(Int_node* t, int k);
};

其他类型又如何呢？每个类中都必须存储一个操作符（这倒简单，本文中假定操作符最长不超过2个字符，所以，可以用长度为3的字符数组来保存），但是如何存储子节点呢？在运行时之前，我们并不知道子节点的类型会是什么，所以我们不能按值存储子节点，必须存储指针。这样，一元和二元节点类如下所示：

CLASS(Unary_node)
{
    
      
  EXTENDS(Expr_node);
  char op[3];   //假设操作符最长不超过2个字符
  Expr_node* opnd;  

  void (*init)(Unary_node* t, const char* a, Expr_node* b);
};


CLASS(Binary_node)
{
    
      
  EXTENDS(Expr_node);
  char op[3];   //假设操作符最长不超过2个字符
  Expr_node* left;
  Expr_node* right;

  void (*init)(Binary_node* t, const char* a, Expr_node* b, Expr_node * c);
};

​ 这个设计方案可以用，不过有一个问题。用户要处理的不是值，而是指针，所以必须记住分配和释放对象。例如，我们需要这么创建表达式树：

  Int_node* int_node1 = Int_node_new();

  Int_node* int_node2 = Int_node_new();

  Int_node* int_node3 = Int_node_new();

  Unary_node* unary_node = Unary_node_new();

  Binary_node* binary_node1 = Binary_node_new();

  Binary_node* binary_node = Binary_node_new();

 

  int_node1->init(int_node1, 5);

  int_node2->init(int_node2, 3);

  int_node3->init(int_node3, 4);

  unary_node->init(unary_node, "-", int_node1);

  binary_node1->init(binary_node1, "+", int_node2, int_node3);

  binary_node->init(binary_node, "*", unary_node, binary_node1);

 

  lw_oopc_delete(int_node1);

  //…… 删除创建的其他节点

也就是说，我们需要去关心每一个节点的创建和释放。我们不仅把内存管理这类烦心事推给了用户，而且对用户来说也没有什么方便的办法来处理这些事情。我们得好好想想办法了。

​ 这里，提供一种解决内存管理问题的思路：引用计数，这里是针对指针，对指针的状况进行计数，对象创建的时候，引用计数为1，凡是指针被赋值了，该指针所指对象的引用计数就自增一，每次指针要释放，都先检查对象的引用计数，让引用计数自减一，如果引用计数为0，则释放该对象。

​ 另外，原先的设计不够高层，用户只能直接针对节点进行操作，没有提供操作子树的概念（这也是用户代码之所以复杂的原因之一），我们发现，通过提供子树的概念，我们不但能够隐藏Expr_node继承层次，而且，对于每一个节点，我们具备了操纵左子树和右子树的能力（原来只能操作左子节点和右子节点）。而这种功能增强完全是建立在面向对象的机制之上，我们并没有引入耦合，在非常自然和轻松的情形下，我们获得了更好的软件组件之间协作的能力，这正是面向对象的魅力所在。

​ 这里，我们把子树的概念用类Expr来表示，由于子树此时成了Expr_node具体类的成员，同样，左右子树在Expr_node中同样是以指针的方式保存，所以，对Expr也需要进行引用计数，代码直接贴上来，细节解说参见注释：

expr.h

// expr.h

#ifndef EXPR_H_INCLUDED_
#define EXPR_H_INCLUDED_

#include "lw_oopc.h"

 

// 表达式节点
ABS_CLASS(Expr_node)
{
    
      
  int use;    // 引用计数
 
  void (*print)(Expr_node* t);    // 打印表达式节点
  void (*finalize)(Expr_node* t);   // 子类通过覆写finalize方法，实现对资源清理行为的定制
};

 

// 表达式（子树的概念），其中，init*方法族提供了构建子树的高层API，方便用户使用

CLASS(Expr)
{
    
      
  int use;     // 引用计数
  Expr_node* p;  // 子树的根节点

 

  // 构建整数表达式（包含一个整数值，无子表达式）
  void (*initInt)(Expr* t, int);

  // 构建一元表达式（包含一个操作符，一个子表达式）
  void (*initUnary)(Expr* t, const char*, Expr*);

  // 构建一元表达式的重载形式(通过传入个整型值参数，构造一个子表达式为整数表达式的一元表达式）
  void (*initUnaryX)(Expr* t, const char*, int);

 

  // 构建二元表达式（包含一个操作符，二个子表达式）
  void (*initBinary)(Expr* t, const char*, Expr*, Expr*);

  // 构建二元表达式的重载形式(通过传入个整型值参数，构造两个子表达式均为整数表达式的二元表达式）
  void (*initBinaryX)(Expr* t, const char*, int, int);

  void (*print)(Expr* t);   // 打印子树
};

 

// 整数表达式节点
CLASS(Int_node)

{
    
      
  EXTENDS(Expr_node);   // 继承Expr_node

  int n;          // 整数值 
 

  // 初始化整数表达式节点（传入整数值）
  void (*init)(Int_node* t, int k);  
};

 

// 一元表达式节点
CLASS(Unary_node)
{
    
      
   EXTENDS(Expr_node);   // 继承Expr_node

   char op[3];        // 假设操作符最长不超过2个字符
   Expr* opnd;        // 子表达式  

   // 初始化一元表达式节点（传入一个操作符和一个子表达式）
   void (*init)(Unary_node* t, const char* a, Expr* b);
};

 

// 二元表达式节点
CLASS(Binary_node)
{
    
      
  EXTENDS(Expr_node);   // 继承Expr_node
 
  char op[3];       // 假设操作符最长不超过2个字符
  Expr* left;       // 左子表达式
  Expr* right;      // 右子表达式

  // 初始化二元表达式节点（传入一个操作符和两个子表达式）
  void (*init)(Binary_node* t, const char* a, Expr* b, Expr* c);
};

#endif

expr.c

//expr.c
//…… // 包含所需头文件
 
//ABS_CTOR表示抽象类的定义开始
ABS_CTOR(Expr_node)  
  cthis->use = 1;       // 构造函数中，将引用计数初始化为
END_ABS_CTOR

  

// Expr_node的析构函数（DTOR/END_DTOR用于实现析构函数语义）
DTOR(Expr_node)
  if (--cthis->use == 0)   // 递减引用计数，如果计数为，释放自己
  {
    
      
	cthis->finalize(cthis); // 释放内存之前先清理资源(其他需要释放的对象）
	return lw_oopc_true;  // 返回true，表示析构成功，可以释放内存
  }

  return lw_oopc_false;   // 返回false，表示析构失败，不能释放内存
END_DTOR

 

// 构建整数表达式（包含一个整数值，无子表达式），n为整数值
void Expr_initInt(Expr* expr, int n)
{
    
      
  Int_node* intNode = Int_node_new(lw_oopc_file_line);
  intNode->init(intNode, n);
  expr->p = SUPER_PTR(intNode, Expr_node);
}

 

//…… // 因篇幅所限，构建一元表达式、二元表达式以及对应的重载形式的函数实现代码省略

// 打印表达式（子树）

void Expr_print(Expr* t)
{
    
      
  Expr_node* p = t->p;
  p->print(p);
}

CTOR(Expr)
FUNCTION_SETTING(initInt, Expr_initInt);
FUNCTION_SETTING(initUnary, Expr_initUnary);
FUNCTION_SETTING(initUnaryX, Expr_initUnaryX);
FUNCTION_SETTING(initBinary, Expr_initBinary);
FUNCTION_SETTING(initBinaryX, Expr_initBinaryX);
FUNCTION_SETTING(print, Expr_print);

  cthis->use = 1;       // 构造函数中，将引用计数初始化为
END_CTOR

 

// Expr的析构函数（DTOR/END_DTOR用于实现析构函数语义）

DTOR(Expr)
  if (--cthis->use == 0)   // 递减引用计数，如果计数为，释放自己
  {
    
      
	Expr_node_delete(cthis->p);
	return lw_oopc_true;
  }

  return lw_oopc_false;
END_DTOR

 

// 整数表达式节点的初始化
void Int_node_init(Int_node* t, int k)
{
    
      
  t->n = k;
}

 

// 整数表达式节点的打印
void Int_node_print(Expr_node* t) 
{
    
      
  Int_node* cthis = SUB_PTR(t, Expr_node, Int_node);

  printf("%d", cthis->n); 
}

 

// 整数表达式节点的资源清理
void Int_node_finalize(Expr_node* t)
{
    
      
  // 什么都不需要做
}

 

CTOR(Int_node)
SUPER_CTOR(Expr_node);
FUNCTION_SETTING(init, Int_node_init);
FUNCTION_SETTING(Expr_node.print, Int_node_print);
FUNCTION_SETTING(Expr_node.finalize, Int_node_finalize);
END_CTOR

 

//…… // 因篇幅所限，一（二）元表达式节点的初始化、打印、资源清理、构造等函数的实现代码省略

main.c

//main.c

#include "stdio.h"

#include "Expr.h"

 

int main()

{
    
      

  Expr* expr = Expr_new();

//…… // 创建expr1、expr2、expr3的代码

 

  expr1->initUnaryX(expr1, "-", 5);
  expr2->initBinaryX(expr2, "+", 3, 4);
  expr3->initBinary(expr3, "*", expr1, expr2);
  expr->initBinary(expr, "*", expr3, expr3);

  

  expr3->print(expr3);
  printf("\n");
  expr->print(expr);
  printf("\n");

 

  Expr_delete(expr);
  //…… // 删除expr3、expr2、expr1的代码
    
  return 0;
}

程序运行的效果如下：

怎么样？效果还不错吧，最重要的是，我们的C语言代码现在已经完全是面向对象的。