/*******************************************************************
1. How to create a binary tree manually for an arithmetic expression
(e.g., "9000 + 6 * 4")
2. How to evaluate an expression (based on its tree representation)
COMP9024 24T2
*******************************************************************/A binary tree is a hierarchical data structure wherein each node can have a maximum of two children,
known as the left child and the right child.
An arithmetic expression (i.e., a string)
"9000 + (6 * 4)"
can be represented as an abstract syntax tree after parsing.
+
/ \
9000 *
/ \
6 4
The abstract syntax tree is a binary tree in this case.
After visiting/traversing each node of the binary tree:
eval("9000 + 6 * 4") == 9024
Its intermediate representation (IR):
t0 = 6 * 4
t1 = 9000 + t0 In this project, we create the binary tree manually.
Postorder traversal is a tree traversal method that adheres to the Left-Right-Root policy.
In this method, each node in the tree is visited in the following sequence:
(1) The left subtree is traversed first.
(2) Then the right subtree is traversed.
(3) Finally, the root node is traversed.
In COMP9024/Tutorials/Week4, we will study how to parse the input string and create the abstract syntax tree with a parser.
1 How to download COMP9024/Trees/BiTree in CSE VLAB
Open a terminal (Applications -> Terminal Emulator)
$ git clone https://github.com/sheisc/COMP9024.git
$ cd COMP9024/Trees/BiTree
BiTree$
2 How to start Visual Studio Code to browse/edit/debug a project.
BiTree$ code
Two configuration files (BiTree/.vscode/launch.json and BiTree/.vscode/tasks.json) have been preset.
In the window of Visual Studio Code, please click "File" and "Open Folder",
select the folder "COMP9024/Trees/BiTree", then click the "Open" button.
click Terminal -> Run Build Task
Open src/expr.c, and click to add a breakpoint (say, line 105).
Then, click Run -> Start Debugging
├── Makefile defining set of tasks to be executed (the input file of the 'make' command)
|
├── README.md introduction to this project
|
├── src containing *.c and *.h
| |
│ ├── expr.c arithmetic expression
│ ├── expr.h
│ └── main.c main()
|
|── images
|
└── .vscode containing configuration files for Visual Studio Code
|
├── launch.json specifying which program to debug and with which debugger,
| used when you click "Run -> Start Debugging"
|
└── tasks.json specifying which task to run (e.g., 'make' or 'make clean')
used when you click "Terminal -> Run Build Task" or "Terminal -> Run Task"Makefile is discussed in COMP9024/C/HowToMake.
In addition to utilizing VS Code, we can also compile and execute programs directly from the command line interface as follows.
COMP9024/Trees/BiTree$ make
COMP9024/Trees/BiTree$ ./main
t0 = 6 * 4
t1 = 9000 + t0
9000 + 6 * 4 == 9024
// Max length of an identifier (e.g., a function or variable name)
#define MAX_ID_LEN 127
// token value
typedef struct {
// e.g, "year", "t0", "t1", "+", "-", "*", "/", "(", ")", ...
char name[MAX_ID_LEN + 1];
// value of an integer, e.g., 2024
long numVal;
} Value;
// In C, an Enum/Enumeration is a custom data type where users can assign names to constant integers.
// Using enums makes it easier for programmers to learn, understand, and maintain the program.
typedef enum {
TK_NA, // 0 By default, the first item has the value 0. Here, NA stands for Not Available.
TK_ADD, // 1 '+'
TK_SUB, // 2 '-'
TK_MUL, // 3 '*'
TK_DIV, // 4 '/'
TK_NUM, // 5 number
TK_LPAREN, // 6 '(' left parenthesis
TK_RPAREN, // 7 ')' right parenthesis
TK_EOF, // 8 end of file
} TokenKind;
/*
The Abstract Syntax Tree Node for an expression.
In an abstract syntax tree, syntactic details such as parentheses in expressions
like "(20 + 30) * 40" are considered redundant and thus ignored.
*
/ \
+ 40
/ \
20 30
*/
struct astExprNode {
/*
1. The kind of an expression node:
an operand (e.g., 300) or an operator (e.g., '+', '-', '*' and '/')
2. To keep it simple, we use the TokenKind as mentioned above
TK_NUM for 300, 400, ...
TK_ADD for '+'
TK_SUB for '-'
TK_MUL for '*'
TK_DIV for '/'
*/
TokenKind op;
/*
The value of the token (a token is a word), consisting of two parts:
1. an integer for representing the node's value (e.g., 300),
2. a C string for representing its name or value (e.g., "+", "t0", "t1", "(", ")", "300", ...)
*/
Value value;
/////////////////////////////////////////////
// e.g., left and right operands of a binary operator (+, -, *, /)
struct astExprNode *leftChild;
struct astExprNode *rightChild;
};
typedef struct astExprNode *AstExprNodePtr;int main(int argc, char **argv, char **env) {
// Create a binary tree
AstExprNodePtr expr = Expression();
// Perform a postorder traversal of the binary tree
long result = EvalExpression(expr);
// Output the result
printf("\n9000 + 6 * 4 == %ld\n", result);
// Free the heap memory
ReleaseAstExpr(expr);
return 0;
}Now, let's manually create the binary tree.
We can see why pointers (addresses) are so important.
A tree node can save/keep/store another node's address, thus establishing a connection from one node to another node.
via a pointer
A tree node -------------------------------> another tree node
pOneNode->leftChild = address of another node
The branch in the following binary tree represents a pointer. via a hyperlink
one.html -------------------------------> two.html
<a href="two.html">Neo</a> +
/ \
9000 *
/ \
6 4
static AstExprNodePtr CreateAstExprNode(TokenKind tk, long numVal, char *operator, AstExprNodePtr left,
AstExprNodePtr right) {
AstExprNodePtr pNode = (AstExprNodePtr) malloc(sizeof(struct astExprNode));
assert(pNode != NULL);
memset(pNode, 0, sizeof(*pNode));
// The kind of an expression node
pNode->op = tk;
if (tk == TK_NUM) { // an operand like 9000
// 9000
pNode->value.numVal = numVal;
// "9000"
snprintf(pNode->value.name, MAX_ID_LEN, "%ld", numVal);
} else { // an operator: + - * /
// A temporary variable's name: "t0", "t1"
snprintf(pNode->value.name, MAX_ID_LEN, "t%d", NewTemp());
}
pNode->leftChild = left;
pNode->rightChild = right;
return pNode;
}
// Now, let's manually create the binary tree.
// We will write a parser to create the tree for us later.
AstExprNodePtr Expression(void) {
AstExprNodePtr left = CreateAstExprNode(TK_NUM, 9000, "", NULL, NULL);
AstExprNodePtr rightLeft = CreateAstExprNode(TK_NUM, 6, "", NULL, NULL);
AstExprNodePtr rightRight = CreateAstExprNode(TK_NUM, 4, "", NULL, NULL);
AstExprNodePtr right = CreateAstExprNode(TK_MUL, 0, "*", rightLeft, rightRight);
AstExprNodePtr root = CreateAstExprNode(TK_ADD, 0, "+", left, right);
return root;
}Perform a postorder traversal of its binary tree.
Postorder traversal is a tree traversal method that adheres to the Left-Right-Root policy.
In this method, each node in the tree is visited in the following sequence:
(1) The left subtree is traversed first.
(2) Then the right subtree is traversed.
(3) Finally, the root node is traversed.
+
/ \
9000 *
/ \
6 4
#define EmitIR printf
// In fact, it is a simple interpreter
long EvalExpression(AstExprNodePtr root) {
assert(root);
if (root->op == TK_NUM) { // 9000, 6, 4
return root->value.numVal;
}
else { // +, -, *, /
assert(root->leftChild);
assert(root->rightChild);
long leftOperand = EvalExpression(root->leftChild);
long rightOperand = EvalExpression(root->rightChild);
// Postorder traversal:
// a tree traversal method that adheres to the Left-Right-Root policy
long result = 0;
switch (root->op) {
case TK_ADD:
result = leftOperand + rightOperand;
EmitIR("%s = %s + %s\n", root->value.name,
root->leftChild->value.name,
root->rightChild->value.name);
break;
case TK_SUB:
result = leftOperand - rightOperand;
EmitIR("%s = %s - %s\n", root->value.name,
root->leftChild->value.name,
root->rightChild->value.name);
break;
case TK_MUL:
result = leftOperand * rightOperand;
EmitIR("%s = %s * %s\n", root->value.name,
root->leftChild->value.name,
root->rightChild->value.name);
break;
case TK_DIV:
result = leftOperand / rightOperand;
EmitIR("%s = %s / %s\n", root->value.name,
root->leftChild->value.name,
root->rightChild->value.name);
break;
default:
break;
}
return result;
}
}
// Release the heap space
void ReleaseAstExpr(AstExprNodePtr root) {
if (root) {
ReleaseAstExpr(root->leftChild);
ReleaseAstExpr(root->rightChild);
// Postorder traversal
free(root);
}
}