我头痛地尝试构建一个表达式树,尤其是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”在哪里? –