Expression Tree - BiTree's application
Introduction
An expression can be converted to a tree, when every operator in the expression is binocular. One who is familiar with Mathematica may also know Mathematica expressions are all pre-order expressions.
PreOrder expressions in mma
This cpp program is used to read a expression and convert to a tree in memory, and calculate its value by means of the tree.
Code
#ifndef LINK_QUEUE_H
#define LINK_QUEUE_H
/*
*
=
*
* Filename: Link-Queue.h
*
* Description: Implement a link queue in C.
*
* Version: 1.0
* Created: 2021/10/20 23:22:12
* Compiler: gcc
* Author: CuSO4_Deposit (Depoze), CuSO4D@protonmail.com
*/
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define FAILURE 0
typedef int Status;
typedef union{
float Number;
char Operator;
}OpElem;
typedef struct{
bool tag;
OpElem Elem;
}QElemtype;
typedef struct QNode{
QElemtype data;
struct QNode* next;
}QNode;
typedef struct{
QNode* front;
QNode* rear;
}LinkQueue;
// Function Declaration
Status InitQueue(LinkQueue& Q);
Status DestroyQueue(LinkQueue& Q);
Status ClearQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemtype& e);
Status EnQueue(LinkQueue& Q, QElemtype e);
Status DeQueue(LinkQueue& Q, QElemtype& e);
Status QueueTraverse(LinkQueue Q, Status (*Visit)(QNode*));
Status TestTraverse(QNode* n);
// Function Implement
Status InitQueue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: InitQueue
* Description: Initialize a Queue. Will allocate memory for pointers.
*
=
*/
Q.front = (QNode*)malloc(sizeof(QNode));
if(!Q.front) return FAILURE;
Q.rear = Q.front;
return SUCCESS;
}
Status DestroyQueue(LinkQueue& Q) {
/*
*
= FUNCTION
* Name: DestroyQueue
* Description: Destroy a Queue. Free all the pointers.
*
=
*/
if (!ClearQueue(Q)) return FAILURE;
free(Q.rear); Q.rear = NULL; //Q.rear and Q.front must point to the
Q.front = NULL; // same address, free once.
return SUCCESS;
}
Status ClearQueue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: ClearQueue
* Description: Clear Q to an emply queue.
*
=
*/
QElemtype temp;
while(!QueueEmpty(Q))
if(!DeQueue(Q, temp)) return FAILURE;
return SUCCESS;
}
int QueueLength(LinkQueue Q){
/*
*
= FUNCTION
* Name: QueueLength
* Description: return the number of nodes in Q.
*
=
*/
int counter = 0;
QNode* cur = Q.front;
while((cur = cur->next))
counter++;
return counter;
}
bool QueueEmpty(LinkQueue Q){
/*
*
= FUNCTION
* Name: QueueEmpty
* Description: return TRUE if Q is empty; else return FALSE.
*
=
*/
if(Q.front->next == NULL) return TRUE;
else return FALSE;
}
Status GetHead(LinkQueue Q, QElemtype& e){
/*
*
= FUNCTION
* Name: GetHead
* Description: return the first element in Q with e.
*
=
*/
if(QueueEmpty(Q)) return FAILURE;
e = (Q.front->next)->data;
return SUCCESS;
}
Status EnQueue(LinkQueue& Q, QElemtype e){
/*
*
= FUNCTION
* Name: EnQueue
* Description: insert e to Queue ('s rear).
*
=
*/
QNode* NewNodePtr = (QNode*)malloc(sizeof(QNode));
if(!NewNodePtr) return FAILURE;
NewNodePtr -> data = e;
NewNodePtr -> next = NULL;
Q.rear -> next = NewNodePtr;
Q.rear = NewNodePtr;
return SUCCESS;
}
Status DeQueue(LinkQueue& Q, QElemtype& e) {
/*
*
= FUNCTION
* Name: DeQueue
* Description: Delete the first element in Q after assigning it to e.
*
=
*/
if (QueueEmpty(Q)) return FAILURE;
e = (Q.front->next)->data;
QNode* FreeHere = Q.front->next;
if (FreeHere == Q.rear) Q.rear = Q.front;
Q.front->next = FreeHere->next;
free(FreeHere); FreeHere = NULL;
return SUCCESS;
}
Status QueueTraverse(LinkQueue Q, Status (*Visit(QNode*))){
/*
*
= FUNCTION
* Name: QueueTraverse
* Description: Traverse Q. To each QNode n, do "Visit(&n);".
*
=
*/
QNode* TraversePtr = Q.front;
while((TraversePtr = TraversePtr -> next))
if(!Visit(TraversePtr)) return FAILURE;
return SUCCESS;
}
Status TestTraverse(QNode* n){
/*
*
= FUNCTION
* Name: TestTraverse
* Description: a test function for QueueTraverse().
*
=
*/
printf("%c\n", n->data);
return SUCCESS;
}
//suggest parentheses around assignment used as truth value/
#endif //#ifndef LINK_QUEUE_H
#ifndef SEQUENCE_STACK_H
#define SEQUENCE_STACK_H
/*
*
=
*
* Filename: Sequence Stack.h
*
* Description: Implement sequence stack in C.
*
* Version: 1.0
* Created: 2021/9/29 23:31:18
* Revision: none
* Compiler: gcc
*
* Author: CuSO4_Deposit (Depoze), CuSO4D@protonmail.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define FAILURE 0
#define InitialSize 50
#define IncrementSize 10
typedef int Status;
typedef float SElemtype;
typedef struct {
SElemtype* base;
SElemtype* top;
int Stacksize;
}SqStack;
//Function Declaration
Status InitStack(SqStack& S);
Status DestroyStack(SqStack& S);
Status ClearStack(SqStack& S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S, SElemtype& e);
Status StackIncrease(SqStack& S);
Status Push(SqStack& S, SElemtype e);
Status Pop(SqStack& S, SElemtype& e);
Status StackTraverse(SqStack S, Status(*Visit)(SElemtype*));
Status Visit(SElemtype* VisitPtr);
//Function Implement
Status InitStack(SqStack& S) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
S.base = (SElemtype*)malloc(InitialSize * sizeof(SElemtype));
S.top = S.base;
S.Stacksize = InitialSize;
return SUCCESS;
}
Status DestroyStack(SqStack& S) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
free(S.base);
S.top = NULL; S.base = NULL;
S.Stacksize = 0;
return SUCCESS;
}
Status ClearStack(SqStack& S) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
S.top = S.base;
return SUCCESS;
}
bool StackEmpty(SqStack S) {
/*
* Precondition: S exists.
* return value: 0:false; 1:true.
*/
if (S.top == S.base)return TRUE;
else return FALSE;
}
int StackLength(SqStack S) {
/*
* Precondition: S exists.
* return value: the number of elem in S.
*/
return S.top - S.base;
}
Status GetTop(SqStack S, SElemtype& e) {
/*
* Precondition: S exists.
* Postcondition: return the top elem with e.
* return value: 0:failure; 1:success.
*/
e = *(S.top - 1);
return SUCCESS;
}
Status StackIncrease(SqStack& S) {
/*
* Precondition: S exists, S is full.
* return value: 0:failure; 1:success.
*/
SElemtype* newptr = (SElemtype*)realloc(S.base, (S.Stacksize + IncrementSize) * sizeof(SElemtype));
if (!newptr) {
printf("Error reallocating space.");
return FAILURE;
}
S.base = newptr;
S.top = S.base + S.Stacksize;
S.Stacksize = S.Stacksize + IncrementSize;
return SUCCESS;
}
Status Push(SqStack& S, SElemtype e) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
if (StackLength(S) == S.Stacksize)StackIncrease(S);
*(S.top++) = e;
return SUCCESS;
}
Status Pop(SqStack& S, SElemtype& e) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
e = *--S.top;
return SUCCESS;
}
Status StackTraverse(SqStack S, Status (*Visit)(SElemtype*)) {
/*
* Precondition: S exists.
* return value: 0:failure; 1:success.
*/
SElemtype* TraversePtr = S.base;
while (TraversePtr != S.top)
if (!Visit(TraversePtr++))return FAILURE;
return SUCCESS;
}
Status Visit(SElemtype* VisitPtr) {
//An example of Visit function used in StackTraverse function.
printf("%c\n", *VisitPtr);
return SUCCESS;
}
//int main()
#endif //#ifndef SEQUENCE_STACK_H
/*
*
=
*
* Filename: BiTree.h
*
* Description: Implemrnt a BiTree in C.
*
* Version: 1.0
* Created: 2021/10/21 18:21:42
* Revision: none
* Compiler: gcc
*
* Author: CuSO4_Deposit (Depoze), CuSO4D@protonmail.com
*/
#ifndef BITREE_H
#define BITREE_H
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SUCCESS 1
#define FAILURE 0
typedef int Status;
typedef char TElemtype;
typedef struct BiTNode{
TElemtype data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode;
typedef BiTNode* QElemtype;
typedef struct QNode{
QElemtype data;
struct QNode* next;
}QNode;
typedef struct{
QNode* front;
QNode* rear;
}LinkQueue;
// Queue Function Declaration
Status InitQueue(LinkQueue& Q);
Status DestroyQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
Status ClearQueue(LinkQueue& Q);
Status EnQueue(LinkQueue& Q, QElemtype e);
Status DeQueue(LinkQueue& Q, QElemtype& e);
// Function Declaration
Status InitBiTree(BiTNode* T);
Status DestroyBiTree(BiTNode*& T);
Status ClearBiTree(BiTNode*& T);
Status CreateBiTree(BiTNode*& T);
bool BiTreeEmpty(BiTNode* T);
int BiTreeDepth(BiTNode* T);
TElemtype Value(BiTNode* T);
Status Assign(BiTNode* T, TElemtype e);
BiTNode* Parent(BiTNode* T);
BiTNode* LeftChild(BiTNode* T);
BiTNode* RightChild(BiTNode* T);
Status InsertChild(BiTNode* T, int LR, TElemtype Value);
Status DeleteChild(BiTNode*& T, int LR);
Status PostorderTraverse(BiTNode* T, Status (*visit)(BiTNode*));
Status LevelorderTraverse(BiTNode* T, Status (*visit)(BiTNode*));
Status InitQueue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: InitQueue
* Description: Initialize a Queue. Will allocate memory for pointers.
*
=
*/
Q.front = (QNode*)malloc(sizeof(QNode));
if(!Q.front) return FAILURE;
Q.front->next = NULL;
Q.rear = Q.front;
return SUCCESS;
}
Status DestroyQueue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: DestroyQueue
* Description: Destroy a Queue. Free all the pointers.
*
=
*/
if(!ClearQueue(Q)) return FAILURE;
free(Q.rear); Q.rear = NULL; //Q.rear and Q.front must point to the
Q.front = NULL; // same address, free once.
return SUCCESS;
}
Status ClearQueue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: ClearQueue
* Description: Clear Q to an emply queue.
*
=
*/
QElemtype temp;
while(!QueueEmpty(Q))
if(!DeQueue(Q, temp)) return FAILURE;
return SUCCESS;
}
Status EnQueue(LinkQueue& Q, QElemtype e){
/*
*
= FUNCTION
* Name: EnQueue
* Description: insert e to Queue ('s rear).
*
=
*/
QNode* NewNodePtr = (QNode*)malloc(sizeof(QNode));
if(!NewNodePtr) return FAILURE;
NewNodePtr -> data = e;
NewNodePtr -> next = NULL;
Q.rear -> next = NewNodePtr;
Q.rear = NewNodePtr;
return SUCCESS;
}
Status DeQueue(LinkQueue& Q, QElemtype& e){
/*
*
= FUNCTION
* Name: DeQueue
* Description: Delete the first element in Q after assigning it to e.
*
=
*/
if(QueueEmpty(Q)) return FAILURE;
e = (Q.front -> next) -> data;
QNode* FreeHere = Q.front -> next;
if (FreeHere == Q.rear) Q.rear = Q.front;
Q.front -> next = FreeHere -> next;
free(FreeHere); FreeHere = NULL;
return SUCCESS;
}
bool QueueEmpty(LinkQueue Q){
/*
*
= FUNCTION
* Name: QueueEmpty
* Description: return TRUE if Q is empty; else return FALSE.
*
=
*/
if(Q.front->next == NULL) return TRUE;
else return FALSE;
}
Status InitBiTree(BiTNode* T){
/*
*
= FUNCTION
* Name: InitBiTree
* Description: Initialize a BiTree, assigning NULL to pointers.
*
=
*/
T->lchild = NULL;
T->rchild = NULL;
return SUCCESS;
}
Status DestroyBiTree(BiTNode*& T){
/*
*
= FUNCTION
* Name: DestroyBiTree
* Description: free memory.
*
=
*/
if(!T) return SUCCESS;
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
free(T); T = NULL;
return SUCCESS;
}
Status PostorderTraverse(BiTNode* T, Status (*visit)(BiTNode*)){
/*
*
= FUNCTION
* Name: PostorderTraverse
* Description: Postorfer traverse a tree. to each node N. execute visit(N);
*
=
*/
if(!T) return SUCCESS;
PostorderTraverse(T->lchild, visit);
PostorderTraverse(T->rchild, visit);
visit(T);
return SUCCESS;
}
Status ClearBiTree(BiTNode*& T){
/*
*
= FUNCTION
* Name: ClearBiTree
* Description: Delete all son nodes, T becomes an empty tree.
*
=
*/
if(!T) return SUCCESS;
ClearBiTree(T->lchild);
ClearBiTree(T->rchild);
DeleteChild(T, 0);
DeleteChild(T, 1);
return SUCCESS;
}
Status CreateBiTree(BiTNode*& T){
/*
*
= FUNCTION
* Name: CreateBiTree
* Description: input a preorder traverse sequence, replace empty tree with '#'.
* Function will create a BiTree with T as its root.
*
=
*/
char temp = '0';
std::cin>>temp;
if (temp == '#'){
T = NULL;
return SUCCESS;
}
else{
if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) return FAILURE;
T->data = temp;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return SUCCESS; //Invalid. just for fixing warning.
}
TElemtype Value(BiTNode* T){
/*
*
= FUNCTION
* Name: Value
* Description: return the data of T.
*
=
*/
return T->data;
}
Status Assign(BiTNode* T, TElemtype e){
/*
*
= FUNCTION
* Name: Assign
* Description: assign e to T->data.
*
=
*/
if(!T) return FAILURE;
T->data = e;
return SUCCESS;
}
Status DeleteChild(BiTNode*& T, int LR){
/*
*
= FUNCTION
* Name: DeleteChlid
* Description: Delete the child of a node. L = 0; R = 1.
*
=
*/
if(LR){
if(!T->rchild) return SUCCESS;
free(T->rchild); T->rchild = NULL;
}
else{ //LR = 1
if(!T->lchild) return SUCCESS;
free(T->lchild); T->lchild = NULL;
}
return SUCCESS;
}
Status InsertChild(BiTNode* T, int LR, TElemtype ChildData){
/*
*
= FUNCTION
* Name: InsertChild
* Description: insert a child to this root. L = 0, R = 1.
* if the place has already got a child, return FALSE.
*
=
*/
if(LR){
if(T->rchild) return FAILURE;
BiTNode* temp = (BiTNode*)malloc(sizeof(BiTNode));
temp->data = ChildData;
temp->lchild = NULL; temp->rchild = NULL;
T->rchild = temp;
}
else{ //LR = 1
if(T->lchild) return FAILURE;
BiTNode* temp = (BiTNode*)malloc(sizeof(BiTNode));
temp->data = ChildData;
temp->lchild = NULL; temp->rchild = NULL;
T->lchild = temp;
}
return SUCCESS;
}
bool BiTreeEmpty(BiTNode* T){
/*
*
= FUNCTION
* Name: BiTreeEmpty
* Description: if BiTree is empty, return TRUE, else return FALSE.
*
=
*/
if(T) return TRUE;
else return FALSE;
}
int BiTreeDepth(BiTNode* T){
/*
*
= FUNCTION
* Name: BiTreeDepth
* Description: return the depth of bitree. (the depth of only a root is 1)
*
=
*/
if(!T) return 0;
int lDepth = BiTreeDepth(T->lchild);
int rDepth = BiTreeDepth(T->rchild);
return lDepth < rDepth
? rDepth + 1
: lDepth + 1;
}
Status LevelorderTraverse(BiTNode* T, Status (*visit)(BiTNode*)){
/*
*
= FUNCTION
* Name: LevelorderTraverse
* Description: Traverse in level order, based on queue.
*
=
*/
LinkQueue Q;
InitQueue(Q);
QElemtype Processing;
if(!T) return SUCCESS;
EnQueue(Q, T);
while (!QueueEmpty(Q)){
DeQueue(Q, Processing);
if(!visit(Processing)) return FAILURE;
if(Processing->lchild) EnQueue(Q, Processing->lchild);
if(Processing->rchild) EnQueue(Q, Processing->rchild);
}
DestroyQueue(Q);
return SUCCESS;
}
BiTNode* Parent(BiTNode* T){
/*
*
= FUNCTION
* Name: Parent
* Description: if T has parent return its parent, else return NULL.
*
=
*/
LinkQueue Q;
InitQueue(Q);
QElemtype Processing;
while (!QueueEmpty(Q)){
DeQueue(Q, Processing);
if(Processing->lchild
T Processing->rchild
T) return Processing;
if(Processing->lchild) EnQueue(Q, Processing->lchild);
if(Processing->rchild) EnQueue(Q, Processing->rchild);
}
return NULL;
DestroyQueue(Q);
}
BiTNode* LeftChild(BiTNode* T){
/*
*
= FUNCTION
* Name: LeftChild
* Description: return the address of T's left child. if it doesn't have one, return NULL.
*
=
*/
return T->lchild;
}
BiTNode* RightChild(BiTNode* T){
/*
*
= FUNCTION
* Name: RightChild
* Description: return the address of T's right child. if it doesn't have one, return NULL.
*
=
*/
return T->rchild;
}
#endif // #ifndef BITREE_H
/*
*
=
*
* Filename: ExpressionTree.cpp
*
* Description: Using tree structure to calculate expressions.
*
* Version: 1.0
* Created: 2021/11/4 23:13:44
* Revision: none
* Compiler: gcc
*
* Author: CuSO4_Deposit (Depoze), CuSO4D@protonmail.com
*/
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include ".\BiTree.h"
#include ".\Link-QueueForExp.h"
#include ".\Sequence-StackForExp.h"
Status Expression2Queue(LinkQueue& Q){
/*
*
= FUNCTION
* Name: InputData
* Description: input a unit of expression, this function will recognize its
* type, tag it and insert it into queue Q.
*
=
*/
bool flag = 0;
float num = 0; float dec = 1; bool point = 0;
char* expression = (char*)malloc(50 * sizeof(char));
// std::cin >> expression; // cin automatically ends input when reads <space>.
fgets(expression, 49, stdin);
char* charptr = expression;
while(!flag){
while(*(charptr)){
if(*charptr == '#'){
flag = 1;
break;
}
if(
*charptr == '+'
*charptr == '-'
*charptr == '*'
*charptr == '/'
){
QElemtype Processing;
Processing.tag = 0;
Processing.Elem.Operator = *charptr;
EnQueue(Q, Processing);
charptr++; break;
}
if(*charptr >= '0' && *charptr <= '9' && point == 0){
num *= 10;
num += (*charptr - 0x30);
}
if(*charptr == '.') point = 1;
if(*charptr >= '0' && *charptr <= '9' && point == 1){
dec /= 10;
num += (*charptr - 0x30) * dec;
}
if(charptr[1] < '0' charptr[1] > '9')
if((point
- (point
0 && charptr[1] != '.')){
QElemtype Processing;
Processing.tag = 1;
Processing.Elem.Number = num;
EnQueue(Q, Processing);
num = 0; dec = 1; point = 0;
charptr++; charptr++; break; //skip the space behind the number
}
charptr++;
}
}
return SUCCESS;
}
Status CalculateVisit(BiTNode* T, SqStack& S) {
if (T->data->tag == 0) {
float num = 0;
float Operand1 = 0; float Operand2 = 0;
Pop(S, Operand1); Pop(S, Operand2);
switch (T->data->Elem.Operator)
{
case '+': num = Operand1 + Operand2; break;
case '-': num = Operand2 - Operand1; break;
case '*': num = Operand1 * Operand2; break;
case '/': if (Operand2 == 0) return FAILURE;
else num = Operand2 / Operand1; break;
default: return 2;
break;
}
Push(S, num);
return SUCCESS;
}
else {// T->data->tag == 1
Push(S, T->data->Elem.Number);
return SUCCESS;
}
}
float CalculateExpTree(BiTNode* T) {
if (!T) return 0;
SqStack S;
InitStack(S);
PostorderTraverse(T, S, CalculateVisit);
float result = 0; Pop(S, result);
return result;
}
int main(){
LinkQueue Q;
InitQueue(Q);
Expression2Queue(Q);
BiTNode* T = (BiTNode*)malloc(sizeof(BiTNode));
InitBiTree(T);
CreateBiTree(T, Q);
printf("%f\n", CalculateExpTree(T));
return 0;
}
Test
input:
+ 8 * 21.3 - 10 8
Output:
C:\WINDOWS\system32\cmd.exe /c (^“D:\Learning\Computer\Data-Structure\Lab\BiTree&Application\ExpressionTree.exe^” )
- 8 * 21.3 - 10 8 # 50.599998 Hit any key to close this window…