[C++/数据结构] 表达式树的建立以及使用

大学数据结构课程 #代码(创建表达式树以及结果运算)

附件:

题目:

Assignment1 (PDF)

Autotest以及代码template文件:

Assignment1Files (ZIP)

Solution:

#include "ExprTree.h"
#include <sstream>
/*debug*/
#include <iostream>

/*
 * Helper function that tests whether a string is a non-negative integer.
 */

bool isdigit(const char &amp; c){

  switch (c) {
  case '0' :
  case '1' :
  case '2' :
  case '3' :
  case '4' :
  case '5' :
  case '6' :
  case '7' :
  case '8' :
  case '9' : return true;
  }

  return false;

}

bool is_number(const std::string &amp; s)
{
    std::string::const_iterator it = s.begin();
    while (it != s.end() &amp;&amp; isdigit(*it)) ++it;
    return !s.empty() &amp;&amp; it == s.end();
}

/*
 * Helper function that converts a string to an int.
 */
int to_number(const std::string &amp; s){
  return atoi(s.c_str());
}

/*
 * Helper function that converts a number to a string.
 */
string to_string(const int &amp; n){
  std::stringstream stream;
  stream &lt;&lt; n;
  return stream.str();
}


/*
 * Helper function that creates a TreeNode with the appropriate operator
 * when given a string that's "+", "-", "*" or "/". If the string is wrong
 * it gives a NoOp value.
 */
TreeNode * createOperatorNode(const string &amp; 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);

}
string displayOP(const Operator &amp; op){

  switch (op)
  {
    case Plus: return "+";
    case Minus: return "-";
    case Times: return "*";
    case Divide: return "/";
    case NoOp: return "NOOP";
    case Value: return "VAR";
  }


}

/*
 * Basic constructor that sets up an empty Expr Tree.
 */
ExprTree::ExprTree(){
  root = NULL;
  _size = 0;
}

/*
 * Constructor that takes a TreeNode and sets up an ExprTree with that node at the root.
 */
int calcSize(TreeNode * r)
{
    int size = 1;
    if(r-&gt;getLeftChild() != NULL) size += calcSize(r-&gt;getLeftChild());
    if(r-&gt;getRightChild() != NULL) size += calcSize(r-&gt;getRightChild());
    return size;
}
ExprTree::ExprTree(TreeNode * r){
    root = r;
    _size = calcSize(r);
}

/*
 * Destructor to clean up the tree.
 */
void DestroyExprTree(TreeNode * r)
{
    if(r != NULL)
    {
      DestroyExprTree(r-&gt;getLeftChild());
      DestroyExprTree(r-&gt;getRightChild());
      delete(r);
    }
}
ExprTree::~ExprTree(){
    DestroyExprTree(root);
}

/*
 * This function takes a string representing an arithmetic expression and breaks
 * it up into components (number, operators, parentheses).
 * It returns the broken up expression as a vector of strings.
 */
//using namespace std;
vector&lt;string&gt; ExprTree::tokenise(string expression){

    //std::cout &lt;&lt; expression &lt;&lt; std::endl;
    std::vector&lt;string&gt; v;
    std::vector&lt;string&gt;::iterator it = v.begin();
    int i = 0;
    int len = expression.length();

    string buffer;//Deal with multible digits number using buffer
    for(i = 0 ; i &lt; len; i++){
      string temp = string(1,expression.at(i));
      if(is_number(temp))
      {
        buffer += temp;//append current digit into buffer.
      }
      else
      {
          if(buffer != "") v.push_back(buffer);
          if(expression.at(i) != ' ') v.push_back(string(1,expression.at(i)));
          //after used, clean buffer.
          buffer = "";
      }
      //for the last element in the string, if avaiable....
      if(i == len-1)
      {
        if(is_number(buffer))
           v.push_back(buffer);
      }

    }

    return v;
}



ExprTree ExprTree::buildTree(vector&lt;string&gt; tokens)
{
    //////////////////////// Infix to posfix ////////////////////////
    int len = tokens.size();
    std::vector&lt;string&gt; postfix;
    //std::vector&lt;string&gt;::iterator it = v.begin();
    std::stack&lt;char&gt; op; // create operator stack
    int i;
    for(i = 0; i &lt; len; i++)
    {
        string current = string(tokens.at(i));

        if(is_number(string(current))){
               postfix.push_back(current);
        }
        else{
           char cchar = current[0];
           char tmp;
           switch(cchar)
           {
              case '(':
                op.push(cchar);
                break;
              case '+':
              case '-':
                while(op.size() !=0)
                {
                  tmp = op.top();
                  op.pop();
                  if(tmp == '(')
                  {
                    op.push(tmp);
                    break;
                  }
                  postfix.push_back(string(1,tmp));
                }
                op.push(cchar);
                break;
              case '*':
              case '/':
                while(op.size() !=0)
                {
                  tmp = op.top();
                  op.pop();
                  if(tmp == '(' || tmp == '+' || tmp == '-')
                  {
                    op.push(tmp);
                    break;
                  }
                  else
                  {
                    postfix.push_back(string(1,tmp));
                  }
                }
                op.push(cchar);
                break;
              case ')':
                while(op.size() !=0)
                {
                  tmp = op.top();
                  op.pop();
                    if(tmp == '(') break;
                    else postfix.push_back(string(1,tmp));
                }
                break;
           }

        }
    }

    //pop all the element in the stack(if avaiable)
    while(op.size()!=0)
    {
      postfix.push_back(string(1,op.top()));
      op.pop();
    }

    // debug code check for the posfix
    /*
    std::cout &lt;&lt; "\nConverted Postfix: ";
    for(vector&lt;string&gt;::const_iterator i = postfix.begin(); i != postfix.end(); ++i)
    {
      std::cout &lt;&lt; *i &lt;&lt; " ";
    }
    */

    std::cout &lt;&lt; "\n";
    //////////////////////// Create a tree by postfix ////////////////////////

    //Create stack &amp; nodes
    std::stack &lt;TreeNode *&gt; s;

    //loop thorugh postfix
    for(vector&lt;string&gt;::const_iterator i = postfix.begin(); i != postfix.end(); ++i)
    {
      TreeNode* node;
      //if it is operar,pop first 2 element and join it with this operator

      if(!is_number(*i)) // if is operator
      {
          node = createOperatorNode(*i);//Create new operator node

          //std::cout &lt;&lt; "Created Node:" &lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; std::endl;
          //std::cout &lt;&lt; "Created Node(Pointer Addr):" &lt;&lt; node &lt;&lt; std::endl;
          node-&gt;setRightChild(s.top());


          //if(s.top()-&gt;isValue()) std::cout &lt;&lt; "Set Node:"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " Right Child-&gt;" &lt;&lt; node-&gt;getRightChild()-&gt;getValue() &lt;&lt; std::endl;
          //if(s.top()-&gt;isOperator()) std::cout &lt;&lt; "Set Node:"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " Right Child-&gt;" &lt;&lt; displayOP(node-&gt;getRightChild()-&gt;getOperator()) &lt;&lt; std::endl;
          //std::cout &lt;&lt; "Right Child Addr-&gt;" &lt;&lt; node-&gt;getRightChild() &lt;&lt; std::endl;


          node-&gt;getRightChild()-&gt;setParent(node);


          //std::cout &lt;&lt; "SetNode:"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " Parent-&gt;" &lt;&lt; node-&gt;getOperator() &lt;&lt; std::endl;


          //--------------------
          s.pop();
          node-&gt;setLeftChild(s.top());

          //if(s.top()-&gt;isValue()) std::cout &lt;&lt; "Set node:"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " Left Chid-&gt;" &lt;&lt; node-&gt;getLeftChild()-&gt;getValue() &lt;&lt; std::endl;
          //if(s.top()-&gt;isOperator()) std::cout &lt;&lt; "Set Node:"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " Left Child-&gt;" &lt;&lt; displayOP(node-&gt;getLeftChild()-&gt;getOperator()) &lt;&lt; std::endl;
          //std::cout &lt;&lt; "Left Child Addr-&gt;" &lt;&lt; node-&gt;getLeftChild() &lt;&lt; std::endl;

          node-&gt;getLeftChild()-&gt;setParent(node);
          //std::cout &lt;&lt; "Set Node :"&lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; " parent-&gt;" &lt;&lt; node-&gt;getRightChild()-&gt;getOperator() &lt;&lt; std::endl;
          s.pop();

          //Last push in this operator node
          s.push(node);
          //std::cout &lt;&lt; "Node:" &lt;&lt; displayOP(node-&gt;getOperator()) &lt;&lt; "is pushed" &lt;&lt; std::endl;

      }
      else //If is number
      {
          node = new TreeNode(to_number(*i));
          //std::cout &lt;&lt; "Create Node:" &lt;&lt; node-&gt;getValue() &lt;&lt; std::endl;
          //std::cout &lt;&lt; "Create Node(Pointer):" &lt;&lt; node &lt;&lt; std::endl;
          s.push(node);
          //std::cout &lt;&lt; "Node:" &lt;&lt; node-&gt;getValue() &lt;&lt; "is pushed" &lt;&lt; std::endl;
      }


    }
    //Last pop out this tree and return it.
    ExprTree * tree = new ExprTree(s.top());


    /*
    std::cout &lt;&lt; "TEST:" &lt;&lt; s.top() &lt;&lt; std::endl;
    std::cout &lt;&lt; "TEST:" &lt;&lt; s.top()-&gt;getRightChild() &lt;&lt; std::endl;
    */
    //then clean the stack
    s.pop();
    return *tree;
}


/*
 * This function takes a TreeNode and does the maths to calculate
 * the value of the expression it represents.
 */
int ExprTree::evaluate(TreeNode * n){
    if(n-&gt;getLeftChild() == NULL &amp;&amp; n-&gt;getRightChild() == NULL)
    {
        return n-&gt;getValue();
    }
    else
    {
        int total =0;
        int l = evaluate(n-&gt;getLeftChild());
        int r = evaluate(n-&gt;getRightChild());

        Operator op = n-&gt;getOperator();
        switch(op)
        {
            case Plus : return l + r;
            case Minus : return l - r;
            case Times : return l * r;
            case Divide : return l / r;
            default: total = l + r;
        }
        return total;
    }

}

/*
 * When called on an ExprTree, this function calculates the value of the
 * expression represented by the whole tree.
 */
int ExprTree::evaluateWholeTree(){
    return ExprTree::evaluate(root);
}

/*
 * Given an ExprTree t, this function returns a string
 * that represents that same expression as the tree in
 * prefix notation.
 */

string preOrderStr(TreeNode * node)
{
    if(node == NULL) return "";
    if(node-&gt;isOperator()) return displayOP(node-&gt;getOperator())+ " " + preOrderStr(node-&gt;getLeftChild())+ " " + preOrderStr(node-&gt;getRightChild());
    else return  to_string(node-&gt;getValue()) + preOrderStr(node-&gt;getLeftChild()) + preOrderStr(node-&gt;getRightChild());
}

string ExprTree::prefixOrder(const ExprTree &amp; t)
{

  return preOrderStr(t.root);

}

/*
 * Given an ExprTree t, this function returns a string
 * that represents that same expression as the tree in
 * infix notation.
 */
string inOrderStr(TreeNode * node)
{
    if(node == NULL) return "";
    if(node-&gt;isOperator()) return  inOrderStr(node-&gt;getLeftChild()) + " " + displayOP(node-&gt;getOperator())+ " "  + inOrderStr(node-&gt;getRightChild());
    else return  inOrderStr(node-&gt;getLeftChild()) + to_string(node-&gt;getValue()) + inOrderStr(node-&gt;getRightChild());
}

string ExprTree::infixOrder(const ExprTree &amp; t){


  return inOrderStr(t.root);

}

/*
 * Given an ExprTree t, this function returns a string
 * that represents that same expression as the tree in
 * postfix notation.
 */
string postOrderStr(TreeNode * node)
{
    if(node == NULL) return "";
    if(node-&gt;isOperator()) return  postOrderStr(node-&gt;getLeftChild()) + " " + postOrderStr(node-&gt;getRightChild()) + " " + displayOP(node-&gt;getOperator()) ;
    else return  postOrderStr(node-&gt;getLeftChild()) + postOrderStr(node-&gt;getRightChild()) + to_string(node-&gt;getValue());
}

string ExprTree::postfixOrder(const ExprTree &amp; t){

  return postOrderStr(t.root);

}

/*
 * Returns the size of the tree. (i.e. the number of nodes in it)
 */
int ExprTree::size(){ return _size; }

/*
 * Returns true if the tree contains no nodes. False otherwise.
 */
bool ExprTree::isEmpty(){ return _size == 0; }

TreeNode * ExprTree::getRoot(){ return root; }

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください