我在尝试构建表达式树时特别头疼，特别是针对treenodes的指针，我不知道如何实现和实际创建存储数据的节点，这本来是很基本的，但是代码却使我感到困惑我。
例如，当我想创建5 + 5的表达式时，它应该是这样的：
+
/ \
5 5
但是，当实现此功能时，我不确定如何开始。如何在根节点中获得运算符，并将数字作为子代？我知道我可以将它们存储在堆栈中并从顶部读取它们，但是矢量标记的类型为string时，设置的父代，左子代和右子代方法仅采用（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.
};
最佳答案
解析表达式的最简单方法是构建递归下降解析器。这由称为表达式，项和因子的相互递归函数组成。一个因数是最小的单位，可以是基数，也可以是开括号，表达式，闭括号（因此可以相互递归）。项是具有乘法和除法运算符的因子的集合，表达式是由正负运算符联接的项的集合。
您需要一元减的特殊规则。
现在，递归下降解析器实际上并未将树构建为内存中的结构。该树在调用模式中是隐式的。但是，如果您想要一棵树，则可以轻松地对其进行修改以构建一棵树。
看看我非常简单的Basic解释器可能会有所帮助
https://github.com/MalcolmMcLean/minibasic
关于c++ - 表达式树实现问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43613422/