Qt Learning Road 51 Boolean Expression Tree Model

兰博

Qt Learning Road 51 Boolean Expression Tree Model [Copy link]

This chapter will be the last part of the custom model. I originally planned to end this part, but I couldn't bear to give up this example. The example of the Boolean expression tree model from the book C++ GUI Programming with Qt 4, 2nd Edition is quite wonderful, complex and practical, so we still end this part with this example. , sans-serif]

This analysis process is often encountered in discrete mathematics, especially for complex Boolean expressions. Similar analysis methods can be applied to a series of operations such as expression simplification and evaluation. At the same time, this technology can also easily analyze whether an expression is a correct Boolean expression. In this example, there are four classes:

Node: the nodes that make up the tree;
BooleanModel: the model of the Boolean expression, which is actually a tree model used to present the Boolean expression as a tree;
BooleanParser: the analyzer for analyzing Boolean expressions;
BooleanWindow: the graphical user interface, where users enter Boolean expressions and analyze them, and finally display the results as a tree.

First, let's take a look at the most basic Node class. This is the node of the analysis tree and the basis of the entire tree.

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, Helvetica, SimSun, sans-serif] The cpp file of Node is also very simple:
Node::Node(Type type, const QString &str)
{
this->type = type;
this->str = str;
parent = 0;
}

Node::~Node()
{
qDeleteAll(children);
}
[color=rgb(0, 204, 255) !important]Copy code
Node It is very similar to a typical tree node: a parent property of Node pointer type, which stores the parent node; a str of QString type, which stores the data. In addition, Node also has a Type property, which indicates the type of the Node, whether it is a morpheme, an operator, or something else; children is a QListType, save all child nodes of this node. Note that in the destructor of the Node class, the global function qDeleteAll() is used. This function deletes all elements in the range [start, end). Therefore, the elements of its parameters must be pointer types. In addition, this function does not assign the pointer to 0 after using delete. Therefore, if you want to call this function outside the destructor, it is recommended to explicitly call the clear() function after the call to reset the pointers of all elements in the list to 0. Although we put this example in the custom model section, the core class of this example is actually BooleanParser. Let's take a look at the code of 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;
}
[color=rgb(0, 204, 255) !important]Copy code
Here we put All the code of BooleanParser is listed. Let's first look at the outline. As a core class, BooleanParser does not contain any code related to the interface. This is another important reason why we put forward this example: layering. For scholars, how to design a project is very important. Layering is one of the important design techniques. Perhaps you have already understood the basic concept of MVC architecture, so I will not repeat it here. Simply put, the so-called layering is Cleanly separate different parts of your program. For example, the BooleanParser class here only processes the Node node and returns the processing result. As for how the processing result is displayed, BooleanParser does not care. From the relevant knowledge of model/view we have learned before, we can also see that the benefits of doing so are: Yes, today we can use QAbstractItemModel to display this result. Tomorrow I find that the graphical interface is not suitable, and I want to use a character interface display instead - no problem, just replace the part used for display.

Get a general idea of the overall design of BooleanParser After that, let's take a closer look at the business logic of this class, that is, the algorithm. Although the algorithm is not the focus here, for an example, this algorithm is the most core part. It also embodies a typical algorithm, and Douzi thinks it is necessary to understand it.

Notice that the BooleanParser class has only one public function Obviously, we must start from here to understand this algorithm. In the Node *parse(const QString &) function, the string of the passed Boolean expression is first saved to avoid directly modifying the parameter (this is also the interface design of the library). A common principle: do not modify parameters); then we remove all spaces and set pos to 0. pos is the current character position when we analyze the Boolean expression string, starting at 0. Then we created the Root node - the tree representation of the Boolean expression. Obviously, there needs to be a root node, so we directly create the root node here. This root node is a complete Boolean expression. ]
[ size=14px]First, let’s take a look at the grammar of Boolean expressions:
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
[color=rgb(0, 204, 255) !important]复制代码
This is a relatively complete Boolean expression grammar. BE→BE OR BE
| BE AND BE
| NOT BE
| (BE)
| Identifier

[color=rgb(0, 204, 255) !important]复制代码

From our simplified grammar, we can see that the Boolean expression BE can be composed of five parts: BE | BE, BE AND BE, NOT BE, (BE) and Identifier, and each part can be recursively defined by BE.

To process a Boolean expression, the or operation has the lowest priority and should be processed last. Once the OR operation is processed, it means that the entire Boolean expression has been processed, so after calling addChild(node, parseOrExpression()), we return the entire node. Let's look at the parseOrExpression() function. To process the OR operation, we must first process the AND operation, so the first sentence of the parseOrExpression() function, we call the parseAndExpression() function. To process the AND operation, we must first process the NOT operation, so the first sentence of parseAndExpression(), we call the parseNotExpression() function. In the parseNotExpression() function, check whether the first character is !. If it is, it means that this expression is a NOT operation, and a NOT node is generated. There may be two different situations for the NOT node:

Subexpression (that is, the part surrounded by parentheses, because this part has the highest priority, it is regarded as a complete subexpression). The subexpression is atomic and requires an independent process. It also generates a node. Its delimiter is ( and ). Between ( and ) is a complete Boolean expression. Recall that the last part of a complete Boolean expression to be processed is the OR operation, so the parseOrExpression() function is called recursively.
Identifier (if the ! symbol is not followed by ( and ), it can only be an identifier, which is determined by the Boolean expression grammar). We use the parseIdentifier() function to obtain this identifier. This function is very simple: starting from the pos position, check one by one whether the current character is a letter. If it is, it means that this character is part of the identifier. If not, it means that the identifier has ended at the position of the previous character (note that it is the position of the previous character, not the current character. When it is detected that the current character is not a letter, it means that the identifier has ended at the previous letter, and the current letter is not part of the identifier). We intercept the string starting from startPos and the length of pos – startPos as the identifier name, instead of the length of pos – startPos + 1.

The NOT node is processed and the function returns to parseAndExpression(). If the NOT node is followed by &&, it is an AND node. We generate an AND node and add the NOT node that has just been processed as its child node. If the && symbol is found all the time, it will be processed as an AND node until it is not &&. The AND node is processed and the node is returned. On the other hand, if the NOT node is not followed by &&, it is not an AND node at all, and the NOT node that has just been processed is directly returned. The function returns to parseOrExpression(). At this time, it is necessary to check whether it is ||. The process is the same as the && type, so it will not be repeated here.

This process looks very complicated, but it is actually very clear: it is executed recursively layer by layer according to the grammar, from the top layer to the bottom layer. If you draw a finite automaton diagram, this process is very concise and clear. This is one of the most important algorithms in the lexical analysis of compiler theory: the recursive descent algorithm. Because this algorithm is concise and clear, many compilers use this algorithm for lexical analysis (of course, its performance is questionable, so mature compilers may choose other algorithms with better performance). Finally, if you find it difficult to understand this part, you might as well skip it. The original content about compiler theory is relatively complicated. :

The most complicated algorithm has been completed, and the next is the BooleanModel class:

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;

}; The BooleanModel class inherits QAbstractItemModel. The reason why it does not inherit QAbstractListModel or QAbstractTableModel is because we want to construct a model with a hierarchical structure. In the constructor, we assign the pointer of the root node to 0, so we provide another function setRootNode() to effectively assign the root node. In the destruction, we directly use the delete operator to release the root node. In the setRootNode() function, we first release the original root node and then assign a value to the root node. At this point we need to notify all views to redraw the interface to show the latest data:
BooleanModel::BooleanModel(QObject *parent)
: QAbstractItemModel(parent)
{
rootNode = 0;
}

BooleanModel::~BooleanModel()
{
delete rootNode;
}

void BooleanModel::setRootNode(Node *node)
{
beginResetModel();
delete rootNode;
rootNode = node;
endResetModel();
}
[color=rgb(0, 204, 255) !important]Copy code
Directly inherit the QAbstractItemModel class, we must implement its five pure virtual functions. The first is the index() function. This function does not need to be implemented in QAbstractTableModel or QAbstractListModel, so those two classes have already implemented it. 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);
}

[color=rgb(0, 204, 255) !important]Copy code

The index() function is used to return the QModelIndex object of the element at row, column, and parent node parent. For the tree model, we are concerned about its parent parameter. In our implementation, if the rootNode, row, or column is illegal, an illegal QModelIndex is returned directly. Otherwise, use the nodeFromIndex() function to get the node with index parent, and then use the children property (this is the property in the Node we defined earlier) to get the child node. If the child node does not exist, return an illegal value; otherwise, return a valid QModelIndex object created by the createIndex() function. For a hierarchical model, only the row and column values cannot determine the position of the element. Therefore, in addition to row and column, QModelIndex also has a void* or int blank property that can store a value. Here we store the pointer of the parent node, so that the element can be located by these three properties. The third parameter of createIndex() here is this internal pointer. So when we define a nodeFromIndex() function ourselves, we must pay attention to using the internalPointer() function of QModelIndex to obtain this internal pointer to locate our node. ::rowCount(const QModelIndex &parent) const BooleanModel::rowCount(const QModelIndex &parent) { // 102, 102, 102, 102; // 102, 102, 102, 102; } } 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;

} [color=rgb(0, 204, 255) !important]Copy code

For rowCount(), it obviously returns the number of child nodes of parentNode; for columnCount(), since our interface is divided into two columns, it always returns 2.

The parent() function returns the index of the parent node to which the child node belongs. We need to start looking from the child node until we find the parent node of its parent node, so that we can locate the parent node and get the position of the child node. The data() function returns the display value of each cell. Based on the previous two chapters, we should be able to easily understand the contents of these two functions. The headerData() function returns the name of the column header. It is the same as before, so I will not repeat it here:

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();
}

[color=rgb(0, 204, 255) !important]Copy code

Finally, we define a helper function:

Node *BooleanModel::nodeFromIndex(const QModelIndex &index) const
{
if (index.isValid()) {
return static_cast(index.internalPointer());
} else {
return rootNode;
}
}

[color=rgb(0, 204, 255) !important]Copy code

As we said above, we use a pointer stored internally in index to get the node corresponding to index. :

Finally, the BooleanWindow class is very simple, so we won’t explain its code in detail:

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);
}

[color=rgb(0, 204, 255) !important]Copy code