我頭痛地嘗試構建一個表達式樹,尤其是treenodes的指針,我不知道如何實現並實際創建存儲應該是數據的節點的線索很基本,但代碼只是讓我困惑。表達式樹實現問題
例如,當我想創建的5 + 5,這是它應該是什麼樣子的表達式:
+
/\
5 5
實施這一然而,當,我不知道如何開始。我如何獲得根節點中的運算符和孩子的數字?我知道我可以將它們存儲在一個堆棧中並讀取頂部,但是集合父,左子節點和右子節點方法僅使用(TreeNode *)參數,而矢量標記則是字符串類型。
此外,TreeNode的構造函數需要一個整數和運算符值,爲什麼?我怎樣才能將這些值作爲根,父母和孩子分別存入各自的節點?
ExprTree.cpp
#include "ExprTree.h"
#include <sstream>
#include <iostream>
TreeNode * createOperatorNode(const string & op){
if (op == "+") return new TreeNode(Plus);
if (op == "-") return new TreeNode(Minus);
if (op == "*") return new TreeNode(Times);
if (op == "/") return new TreeNode(Divide);
return new TreeNode(NoOp);
}
/*
* Basic constructor that sets up an empty Expr Tree.
*/
ExprTree::ExprTree(){
this->root = NULL;
this-> _size = 0;
}
/*
* Constructor that takes a TreeNode and sets up an ExprTree with that node at the root.
*/
ExprTree::ExprTree(TreeNode * r){
this->root = r;
}
ExprTree ExprTree::buildTree(vector<string> tokens){
// the tokens are the broken up arithimec expression
i.e
5
+
5
// not sure what to do here, i've tried using stacks but i wasn't sure how to get the stored data into the nodes.
}
TreeNode.cpp
#include "TreeNode.h"
TreeNode::TreeNode(Operator o){
op = o;
parent = 0;
leftChild = 0;
rightChild = 0;
}
TreeNode::TreeNode(int val){
op = Value;
value = val;
parent = 0;
leftChild = 0;
rightChild = 0;
}
TreeNode.h
#include <string>
#include <sstream>
enum Operator {Value, Plus, Minus, Times, Divide, NoOp};
class TreeNode {
private:
Operator op; //If this node represents an operator, this is where it's stored.
//It can take values from the Operator enum (i.e. Plus, Minus, etc.)
//If it represents a value, use the Value value. :D
int value; //If this node stores an actual number, this is it.
TreeNode * parent; //Pointer to the parent.
TreeNode * leftChild; //Pointer to the left child of this node.
TreeNode * rightChild; //Pointer to the right child of this node.
public:
TreeNode(Operator); //Constructor to use for +, -, * and /.
//Example: TreeNode(Plus);
TreeNode(int); //Constructor to use for actual numbers.
//Example: TreeNode(5);
void setParent(TreeNode *); //Set the parent pointer.
void setLeftChild(TreeNode *); //Set the left child pointer.
void setRightChild(TreeNode *); //Set the right child pointer.
TreeNode * getParent(); //Get the parent pointer.
TreeNode * getLeftChild(); //Get the left child pointer.
TreeNode * getRightChild(); //Get the right child pointer.
int getValue(); //Returns the stored value;
Operator getOperator(); //Returns the stored operator.
bool isValue(); //Returns true if this node is a Value node.
bool isOperator(); //Returns truee if this node is Plus, Minus, Times or Divide node.
std::string toString(); //Returns a simple string representation of the node.
};
「ExprTree.h」在哪裏? –