#（51）：布爾表達式樹模型 本章將會是自定義模型的最后一部分。原本打算結束這部分內容，不過實在不忍心放棄這個示例。來自于 C++ GUI Programming with Qt 4, 2nd Edition 這本書的布爾表達式樹模型的示例相當精彩，復雜而又不失實用性，所以我們還是以這個例子結束這部分內容。 這個例子是將布爾表達式分析成一棵樹。這個分析過程在離散數學中經常遇到，特別是復雜的布爾表達式。類似的分析方法可以套用于表達式化簡、求值等一系列的運算。同時，這個技術也可以很方便地分析一個表達式是不是一個正確的布爾表達式。在這個例子中，一共有四個類： * `Node`：組成樹的節點； * `BooleanModel`：布爾表達式的模型，實際上這是一個樹狀模型，用于將布爾表達式形象地呈現為一棵樹； * `BooleanParser`：分析布爾表達式的分析器； * `BooleanWindow`：圖形用戶界面，用戶在此輸入布爾表達式并進行分析，最后將結果展現成一棵樹。 首先，我們來看看最基礎的`Node`類。這是分析樹的節點，也是構成整棵樹的基礎。 ~~~ class Node { public: enum Type { Root, OrExpression, AndExpression, NotExpression, Atom, Identifier, Operator, Punctuator }; Node(Type type, const QString &str = ""); ~Node(); Type type; QString str; Node *parent; QList<Node *> children; }; ~~~ `Node`的 cpp 文件也非常簡單： ~~~ Node::Node(Type type, const QString &str) { this->type = type; this->str = str; parent = 0; } Node::~Node() { qDeleteAll(children); } ~~~ `Node`很像一個典型的樹的節點：一個`Node`指針類型的 parent 屬性，保存父節點；一個`QString`類型的 str，保存數據。另外，`Node`還有一個`Type`屬性，指明這個`Node`的類型，是一個詞素，還是操作符，或者其他什么東西；`children`是`QList<Node *>`類型，保存這個 node 的所有子節點。注意，在 Node 類的析構函數中，使用了`qDeleteAll()`這個全局函數。這個函數是將 [start, end) 范圍內的所有元素進行 delete 運算。因此，它的參數的元素必須是指針類型的。并且，這個函數使用 delete 之后并不會將指針賦值為 0，所以，如果要在析構函數之外調用這個函數，建議在調用之后顯示的調用`clear()`函數，將列表所有元素的指針重置為 0。 雖然我們將這個例子放在自定義模型這部分，但實際上這個例子的核心類是`BooleanParser`。我們來看一下`BooleanParser`的代碼： ~~~ // booleanparser.h class BooleanParser { public: Node *parse(const QString &expr); private: Node *parseOrExpression(); Node *parseAndExpression(); Node *parseNotExpression(); Node *parseAtom(); Node *parseIdentifier(); void addChild(Node *parent, Node *child); void addToken(Node *parent, const QString &str, Node::Type type); bool matchToken(const QString &str) const; QString in; int pos; }; // booleanparser.cpp Node *BooleanParser::parse(const QString &expr) { in = expr; in.replace(" ", ""); pos = 0; Node *node = new Node(Node::Root); addChild(node, parseOrExpression()); return node; } Node *BooleanParser::parseOrExpression() { Node *childNode = parseAndExpression(); if (matchToken("||")) { Node *node = new Node(Node::OrExpression); addChild(node, childNode); while (matchToken("||")) { addToken(node, "||", Node::Operator); addChild(node, parseAndExpression()); } return node; } else { return childNode; } } Node *BooleanParser::parseAndExpression() { Node *childNode = parseNotExpression(); if (matchToken("&&")) { Node *node = new Node(Node::AndExpression); addChild(node, childNode); while (matchToken("&&")) { addToken(node, "&&", Node::Operator); addChild(node, parseNotExpression()); } return node; } else { return childNode; } } Node *BooleanParser::parseNotExpression() { if (matchToken("!")) { Node *node = new Node(Node::NotExpression); while (matchToken("!")) addToken(node, "!", Node::Operator); addChild(node, parseAtom()); return node; } else { return parseAtom(); } } Node *BooleanParser::parseAtom() { if (matchToken("(")) { Node *node = new Node(Node::Atom); addToken(node, "(", Node::Punctuator); addChild(node, parseOrExpression()); addToken(node, ")", Node::Punctuator); return node; } else { return parseIdentifier(); } } Node *BooleanParser::parseIdentifier() { int startPos = pos; while (pos < in.length() && in[pos].isLetterOrNumber()) ++pos; if (pos > startPos) { return new Node(Node::Identifier, in.mid(startPos, pos - startPos)); } else { return 0; } } void BooleanParser::addChild(Node *parent, Node *child) { if (child) { parent->children += child; parent->str += child->str; child->parent = parent; } } void BooleanParser::addToken(Node *parent, const QString &str, Node::Type type) { if (in.mid(pos, str.length()) == str) { addChild(parent, new Node(type, str)); pos += str.length(); } } bool BooleanParser::matchToken(const QString &str) const { return in.mid(pos, str.length()) == str; } ~~~ 這里我們一次把`BooleanParser`的所有代碼全部列了出來。我們首先從輪廓上面來看一下，`BooleanParser`作為核心類，并沒有摻雜有關界面的任何代碼。這是我們提出這個例子的另外一個重要原因：分層。對于初學者而言，如何設計好一個項目至關重要。分層就是其中一個重要的設計手法。或許你已經明白了 MVC 架構的基本概念，在這里也不再贅述。簡單提一句，所謂分層，就是將程序的不同部分完全分離。比如這里的`BooleanParser`?類，僅僅是處理`Node`的節點，然后返回處理結果，至于處理結果如何顯示，`BooleanParser`不去關心。通過前面我們了解到的?model/view 的相關知識也可以看出，這樣做的好處是，今天我們可以使用`QAbstractItemModel`?來顯示這個結果，明天我發現圖形界面不大合適，我想換用字符界面顯示——沒問題，只需要替換掉用于顯示的部分就可以了。 大致了解了`BooleanParser`的總體設計思路（也就是從顯示邏輯完全剝離開來）后，我們詳細看看這個類的業務邏輯，也就是算法。雖然算法不是我們這里的重點，但是針對一個示例而言，這個算法是最核心的部分，并且體現了一類典型的算法，豆子覺得還是有必要了解下。 注意到`BooleanParser`?類只有一個公共函數，顯然我們必須從這里著手來理解這個算法。在`Node * parse(const QString &)`函數中，首先將傳入的布爾表達式的字符串保存下來，避免直接修改參數（這也是庫的接口設計中常見的一個原則：不修改參數）；然后我們將其中的空格全部去掉，并將?pos 設為 0。pos 就是我們在分析布爾表達式字符串時的當前字符位置，起始為 0。之后我們創建了 Root?節點——布爾表達式的樹狀表達，顯然需要有一個根節點，所以我們在這里直接創建根節點，這個根節點就是一個完整的布爾表達式。 首先我們先來看看布爾表達式的文法： ~~~ BE→ BE OR BE | BE AND BE | NOT BE | (BE) | RE | true | false RE→ RE RELOP RE | (RE) | E E → E op E | -E | (E) | Identifier | Number ~~~ 這是一個相對比較完整的布爾表達式文法。這里我們只使用其中一部分： ~~~ BE→ BE OR BE | BE AND BE | NOT BE | (BE) | Identifier ~~~ 從我們簡化的文法可以看出，布爾表達式 BE 可以由 BE | BE、BE AND BE、NOT BE、(BE) 和 Identifier 五部分組成，而每一部分都可以再遞歸地由 BE 進行定義。 接下來看算法的真正核心：我們按照上述文法來展開算法。要處理一個布爾表達式，或運算的優先級是最低，應該最后被處理。一旦或運算處理完畢，意味著整個布爾表達式已經處理完畢，所以我們在調用了?`addChild(node, parseOrExpression())`之后，返回整個 node。下面來看`parseOrExpression()`函數。要想處理 OR 運算，首先要處理 AND?運算，于是`parseOrExpression()`函數的第一句，我們調用了`parseAndExpression()`函數。要想處理 AND?運算，首先要處理 NOT?運算，于是`parseAndExpression()`的第一句，我們調用了`parseNotExpression()`函數。在`parseNotExpression()`函數中，檢查第一個字符是不是 !，如果是，意味著這個表達式是一個 NOT 運算，生成 NOT 節點。NOT 節點可能會有兩種不同的情況： 1. 子表達式（也就是用括號包圍起來的部分，由于這部分的優先級最高，所以看做是一個完整的子表達式），子表達式是原子性的，需要一個獨立的處理，也要生成一個節點，其分隔符是 ( 和 )。( 和 ) 之間又是一個完整的布爾表達式，回憶一下，一個完整的布爾表達式最后要處理的部分是 OR 運算，因此調用`parseOrExpression()`函數進行遞歸。 2. 標識符（如果 !?符號后面不是 ( 和 )，則只能是一個標識符，這是布爾表達式文法決定的），我們使用`parseIdentifier()`函數來獲得這個標識符。這個函數很簡單：從?pos 位置開始一個個檢查當前字符是不是字母，如果是，說明這個字符是標識符的一部分，如果不是，說明標識符已經在上一個字符的位置結束（注意，是**上一個字符**的位置，而不是當前字符，當檢測到當前字符不是字母時，說明標識符已經在上一個字母那里結束了，當前字母不屬于標識符的一部分），我們截取?startPos 開始，pos – startPos 長度的字符串作為標識符名稱，而不是 pos – startPos + 1 長度。 NOT?節點處理完畢，函數返回到`parseAndExpression()`。如果 NOT?節點后面是 &&，說明是 AND?節點。我們生成一個 AND?節點，把剛剛處理過的 NOT?節點添加為其子節點，如果一直找到了 &&?符號，就要一直作為 AND?節點處理，直到找到的不是 &&，AND?節點處理完畢，返回這個 node。另一方面，如果 NOT 節點后面不是 &&，說明根本不是 AND?節點，則直接把剛剛處理過的 NOT?節點返回。函數重新回到 parseOrExpression() 這里。此時需要檢查是不是 ||，其過程同 && 類型，這里不再贅述。 這個過程看起來非常復雜，實際非常清晰：一層一層按照文法遞歸執行，從最頂層一直到最底層。如果把有限自動機圖示畫出來，這個過程非常簡潔明了。這就是編譯原理的詞法分析中最重要的算法之一：**遞歸下降算法**。由于這個算法簡潔明了，很多編譯器的詞法分析都是使用的這個算法（當然，其性能有待商榷，所以成熟的編譯器很可能選擇了其它性能更好的算法）。最后，如果你覺得對這部分理解困難，不妨跳過，原本有關編譯原理的內容都比較復雜。 最復雜的算法已經完成，接下來是`BooleanModel`?類： ~~~ class BooleanModel : public QAbstractItemModel { public: BooleanModel(QObject *parent = 0); ~BooleanModel(); void setRootNode(Node *node); QModelIndex index(int row, int column, const QModelIndex &parent) const; QModelIndex parent(const QModelIndex &child) const; int rowCount(const QModelIndex &parent) const; int columnCount(const QModelIndex &parent) const; QVariant data(const QModelIndex &index, int role) const; QVariant headerData(int section, Qt::Orientation orientation, int role) const; private: Node *nodeFromIndex(const QModelIndex &index) const; Node *rootNode; }; ~~~ `BooleanModel`類繼承了`QAbstractItemModel`。之所以不繼承`QAbstractListModel`或者`QAbstractTableModel`，是因為我們要構造一個帶有層次結構的模型。在構造函數中，我們把根節點的指針賦值為 0，因此我們提供了另外的一個函數`setRootNode()`，將根節點進行有效地賦值。而在析構中，我們直接使用 delete 操作符將這個根節點釋放掉。在`setRootNode()`函數中，首先我們釋放原有的根節點，再將根節點賦值。此時我們需要通知所有視圖對界面進行重繪，以表現最新的數據： ~~~ BooleanModel::BooleanModel(QObject *parent) : QAbstractItemModel(parent) { rootNode = 0; } BooleanModel::~BooleanModel() { delete rootNode; } void BooleanModel::setRootNode(Node *node) { beginResetModel(); delete rootNode; rootNode = node; endResetModel(); } ~~~ 直接繼承`QAbstractItemModel`類，我們必須實現它的五個純虛函數。首先是`index()`函數。這個函數在`QAbstractTableModel`或者`QAbstractListModel`中不需要實現，因此那兩個類已經實現過了。但是，因為我們現在繼承的`QAbstractItemModel`，必須提供一個合適的實現： ~~~ QModelIndex BooleanModel::index(int row, int column, const QModelIndex &parent) const { if (!rootNode || row < 0 || column < 0) return QModelIndex(); Node *parentNode = nodeFromIndex(parent); Node *childNode = parentNode->children.value(row); if (!childNode) return QModelIndex(); return createIndex(row, column, childNode); } ~~~ `index()`函數用于返回第 row 行，第 column 列，父節點為 parent 的那個元素的`QModelIndex`對象。對于樹狀模型，我們關注的是其 parent 參數。在我們實現中，如果 rootNode 或者 row 或者 column 非法，直接返回一個非法的`QModelIndex`。否則的話，使用`nodeFromIndex()`函數取得索引為 parent 的節點，然后使用`children`屬性（這是我們前面定義的`Node`里面的屬性）獲得子節點。如果子節點不存在，返回一個非法值；否則，返回由`createIndex()`函數創建的一個有效的`QModelIndex`對象。對于具有層次結構的模型，只有 row 和 column 值是不能確定這個元素的位置的，因此，`QModelIndex`中除了 row 和 column 之外，還有一個`void *`或者 int 的空白屬性，可以存儲一個值。在這里我們就把父節點的指針存入，這樣，就可以由這三個屬性定位這個元素。這里的`createIndex()`第三個參數就是這個內部使用的指針。所以我們自己定義一個`nodeFromIndex()`函數的時候要注意使用`QModelIndex`的`internalPointer()`函數獲得這個內部指針，從而定位我們的節點。 `rowCount()`和`columnCount()`兩個函數相對簡單： ~~~ int BooleanModel::rowCount(const QModelIndex &parent) const { if (parent.column() > 0) return 0; Node *parentNode = nodeFromIndex(parent); if (!parentNode) return 0; return parentNode->children.count(); } int BooleanModel::columnCount(const QModelIndex & /* parent */) const { return 2; } ~~~ 對于`rowCount()`，顯然返回的是 parentNode 的子節點的數目；對于`columnCount()`，由于我們界面分為兩列，所以始終返回 2。 `parent()`函數返回子節點所屬的父節點的索引。我們需要從子節點開始尋找，直到找到其父節點的父節點，這樣才能定位到這個父節點，從而得到子節點的位置。而`data()`函數則要返回每個單元格的顯示值。在前面兩章的基礎之上，我們應該可以很容易地理解這兩個函數的內容。`headerData()`函數返回列頭的名字，同前面一樣，這里就不再贅述了： ~~~ QModelIndex BooleanModel::parent(const QModelIndex &child) const { Node *node = nodeFromIndex(child); if (!node) return QModelIndex(); Node *parentNode = node->parent; if (!parentNode) return QModelIndex(); Node *grandparentNode = parentNode->parent; if (!grandparentNode) return QModelIndex(); int row = grandparentNode->children.indexOf(parentNode); return createIndex(row, 0, parentNode); } QVariant BooleanModel::data(const QModelIndex &index, int role) const { if (role != Qt::DisplayRole) return QVariant(); Node *node = nodeFromIndex(index); if (!node) return QVariant(); if (index.column() == 0) { switch (node->type) { case Node::Root: return tr("Root"); case Node::OrExpression: return tr("OR Expression"); case Node::AndExpression: return tr("AND Expression"); case Node::NotExpression: return tr("NOT Expression"); case Node::Atom: return tr("Atom"); case Node::Identifier: return tr("Identifier"); case Node::Operator: return tr("Operator"); case Node::Punctuator: return tr("Punctuator"); default: return tr("Unknown"); } } else if (index.column() == 1) { return node->str; } return QVariant(); } QVariant BooleanModel::headerData(int section, Qt::Orientation orientation, int role) const { if (orientation == Qt::Horizontal && role == Qt::DisplayRole) { if (section == 0) { return tr("Node"); } else if (section == 1) { return tr("Value"); } } return QVariant(); } ~~~ 最后是我們定義的一個輔助函數： ~~~ Node *BooleanModel::nodeFromIndex(const QModelIndex &index) const { if (index.isValid()) { return static_cast<Node *>(index.internalPointer()); } else { return rootNode; } } ~~~ 正如我們上面所說的那樣，我們利用 index 內部存儲的一個指針來獲取 index 對應的節點。 最后，`BooleanWindow`?類非常簡單，我們不再詳細解釋它的代碼： ~~~ BooleanWindow::BooleanWindow() { label = new QLabel(tr("Boolean expression:")); lineEdit = new QLineEdit; booleanModel = new BooleanModel(this); treeView = new QTreeView; treeView->setModel(booleanModel); connect(lineEdit, SIGNAL(textChanged(const QString &)), this, SLOT(booleanExpressionChanged(const QString &))); QGridLayout *layout = new QGridLayout; layout->addWidget(label, 0, 0); layout->addWidget(lineEdit, 0, 1); layout->addWidget(treeView, 1, 0, 1, 2); setLayout(layout); setWindowTitle(tr("Boolean Parser")); } void BooleanWindow::booleanExpressionChanged(const QString &expr) { BooleanParser parser; Node *rootNode = parser.parse(expr); booleanModel->setRootNode(rootNode); } ~~~ 這樣，我們的布爾表達式樹模型已經創建完畢。下面來運行一下看看效果： [](http://files.devbean.net/images/2013/05/boolean-parser.png) 最后，我們附上整個項目的代碼：[下載](http://files.devbean.net/code/booleanparser.zip)