c++ - 如何使用 vector 字符串标记构建表达式树？

Question

几个小时以来，我一直在为这个问题苦苦思索，似乎找不到解决它的方法。基本上我试图插入一个分解的算术字符串表达式，例如。 "12""*""15"转换为二进制表达式树节点。

#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;
}

void TreeNode::setParent(TreeNode * p){ parent = p; }

void TreeNode::setLeftChild(TreeNode * l){

  if (op != Value){
    leftChild = l;
  }

}

void TreeNode::setRightChild(TreeNode * r){

  if (op != Value){
    rightChild = r;
  }

}

TreeNode * TreeNode::getParent(){ return parent; }

TreeNode * TreeNode::getLeftChild(){ return leftChild; }

TreeNode * TreeNode::getRightChild(){ return rightChild; }

int TreeNode::getValue(){ return value; }

Operator TreeNode::getOperator(){ return op; }

bool TreeNode::isValue(){ return op == Value; }

bool TreeNode::isOperator(){ return op != Value && op != NoOp; }

std::string TreeNode::toString(){

  if (isValue()){

    std::stringstream stream;
    stream << getValue();
    return stream.str();

  }

  switch (op){

  case Value : return "val";
  case Plus : return "+";
  case Minus : return "-";
  case Times : return "*";
  case Divide : return "/";
  case NoOp : return "";
  }

}

ExprTree.cpp

/*
 * Basic constructor that sets up an empty Expr Tree.
 */
ExprTree::ExprTree(){


}

/*
 * Constructor that takes a TreeNode and sets up an ExprTree with that node at the root.
 */
ExprTree::ExprTree(TreeNode * r){

    this->root = r;
}

/*
 * Destructor to clean up the tree.
 */
ExprTree::~ExprTree(){


}

/*
 * This function takes a vector of strings representing an expression (as produced
 * by tokenise(string), and builds an ExprTree representing the same expression.
 */
ExprTree ExprTree::buildTree(vector<string> tokens){

         //function in question
    }

该 vector 包含一个拆分的算术表达式(我没有添加该函数，因为它有点长)，它意味着存储在树节点中以创建一个表达式树，其中运算符(+、-、* ) 是父节点或根节点，数字是叶子。问题是能够分离数字并将它们插入左右叶子，迭代不允许我这样做，使用 for 循环。

Answer 1

您正在寻找的东西称为“解析器”，它将获取 token 流并输出 AST。这是编译器构造的一个巨大领域，有许多不同的方法。

Dragon Book (在网上也很容易找到 PDF 版本)是我学到很多理论的方式，我仍然强烈推荐它作为对该主题的一个很好的介绍。

在线进行研究，从 Wikipedia 开始并了解一般方法和不同方法。然后，您可以更具体地搜索您认为可能适合的某些类型的解析器。

对于简单的表达式，shift-reduce 解析器很常见，但我的 goto 选项是 Pratt 的自顶向下运算符优先级解析器，我发现这是一种非常简洁的方法(this 是一个很好的解释)。