CODEWITHSUNDEEP
c++algorithmdata-structuresexpressionbinary-tree
eternal beginner
eternal beginner

Reputation: 41

How to build an expression tree with vector string tokens?

I've been banging my head over this problem for hours now and can't seem to find a way to complete it. Basically i'm trying to insert a broken up arithmetic string expression eg. "12" "*" "15" into binary expression treeNodes.

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

The vector holds a split up arithmetic expression (i didn't add the function because it's a bit long) which is meant to be stored in the tree nodes to create an expression tree, where the operators (+, -, *) are parent or root nodes and the numbers are leafs. The problem is being able to segregate the numbers and insert them into left and right leafs, iteration doesn't allow me to do this, using a for loop.

Upvotes: 0

Views: 1080

Answers (1)

Matt
Matt

Reputation: 7160

What you are looking for is called a "parser", which will take the token stream and output an AST. This is a huge field in compiler construction, with many different methods.

The Dragon Book (very easy to find PDF versions online as well) was how I learnt a lot of the theory, and I'd still highly recommend it as a good introduction to the subject.

Doing your research online, start with Wikipedia and get an idea of the general approach and different methods. You can then google more specifically for certain types of parser that you think might be suited.

For simple expressions, shift-reduce parsers are common, but my goto option is Pratt's Top Down Operator Precedence Parser which I find is an incredibly neat approach (this is a nice explanation).

Upvotes: 1

Related Questions