Thread: Please Excuse My Dear Aunt Sally (Expression Tree Help)

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    29

    Please Excuse My Dear Aunt Sally (Expression Tree Help)

    I am trying to make a calculator but since I am doing this on my own spare time, in the summer, I have no where to turn to but here for help.

    I know the order in which the data must be inserted into the tree but I am stuck in implementing a function that does it. So far I am thinking that the constructor of the ExpressionTree accepts the Equation and the Root node's Node->Insert function is called and recursively puts stuff into the tree's branches.

    So far I only have this. It is just a short test of what I have so far that adds 5 + 3 and outputs 8 to let you all know what I am sort of going for.

    Can you offer me any suggestions. Thank you for your time.

    Main.cpp
    Code:
    #include <iostream>
    
    #include "ExpressionTree.hpp"
    
    int main()
    {
    	ExpresionTree Tree("");
    	
    	Tree.Root = new Node();
    	Tree.Root->type = 1;
    	Tree.Root->Data = "+";
    	
    	Tree.Root->Left = new Node();
    	Tree.Root->Right = new Node();
    	
    	Tree.Root->Left->type  = 0;
    	Tree.Root->Right->type  = 0;
    	
    	Tree.Root->Left->Data  = "5";
    	Tree.Root->Right->Data  = "3";	
    	
    	std::cout << Tree.Value();
    	
    
    	std::cin.get();
    	return 0;
    }
    StringFunctions.hpp
    Code:
    #ifndef STRING_FUNCTIONS_H
    #define STRING_FUNCTIONS_H
    
    #include <sstream>
    #include <cmath>
    
    std::string DoubleToString(double num);
    double StringToDouble(std::string str);
    
    #endif
    StringFunctions.cpp
    Code:
    #include "StringFunctions.hpp"
    
    double StringToDouble(std::string str)
    {
    	double num;
    	std::istringstream is(str);
    	is >> num;
    	return num;
    }
    
    std::string DoubleToString(double num)
    {
    	std::stringstream strm;
    	strm << num;
    	return strm.str();
    }
    ExpressionTree.hpp
    Code:
    #ifndef EXPRESSION_TREE_H
    #define EXPRESSION_TREE_H
    
    #include <iostream>
    #include <cmath>
    
    #include "StringFunctions.hpp"
    
    #define TYPE_NUMBER		0
    #define TYPE_OPERATOR	1
    #define TYPE_FUNCTION 	2
    
    class Node
    {
    public:
    	Node();
        Node(std::string Expression);
        int type;
        Node *Left;
        Node *Right;
        Node *Middle;
        std::string Data;
        int Insert(std::string Expression);
    };
    
    class ExpresionTree
    {
    public:
        ExpresionTree(std::string Expression);
    	~ExpresionTree();
    	
    	std::string Value();
    	std::string GetValue(Node* n);
    
        void Clear(Node *n);
    	Node *Root;
    };
    
    #endif
    ExpressionTree.cpp
    Code:
    #include "ExpressionTree.hpp"
    
    Node::Node() {}
    
    Node::Node(std::string Expression)
    {
    	this->Insert(Expression);
    }
    
    int Node::Insert(std::string Expression)
    {
        
    
    }
    
    ExpresionTree::ExpresionTree(std::string Expression)
    {
    
    
    }
    
    ExpresionTree::~ExpresionTree()
    {
    	Clear(Root);
    }
    
    void ExpresionTree::Clear(Node *n)
    {
        if(n)
        {
            Clear(n->Left);
            Clear(n->Right);
            Clear(n->Middle);
            delete n;
        }
    }
    std::string ExpresionTree::Value()
    {
    	return ExpresionTree::GetValue(Root);
    }
    
    std::string ExpresionTree::GetValue(Node *n)
    {
    	if (n->type == TYPE_NUMBER)
    	{
    		return n->Data;
    	}
    	else if (n->type == TYPE_FUNCTION)
    	{
    		double middlevalue = StringToDouble(GetValue(n->Middle));
    		std::string finalvalue;
    		
    		if (n->Data == "()")
    		{
    			finalvalue = DoubleToString((middlevalue));
    		}		
    		else if (n->Data == "cos")
    		{
    			finalvalue = DoubleToString(cos(middlevalue));
    		}
    		else if (n->Data == "sin")
    		{
    			finalvalue = DoubleToString(sin(middlevalue));
    		}
    		else if (n->Data == "tan")
    		{
    			finalvalue = DoubleToString(tan(middlevalue));
    		}
    		else if (n->Data == "sqrt")
    		{
    			finalvalue = DoubleToString(sqrt(middlevalue));
    		}
    		else if (n->Data == "abs")
    		{
    			finalvalue = DoubleToString(fabs(middlevalue));
    		}
    	}
    	else if (n->type == TYPE_OPERATOR)
    	{
    		double leftvalue = StringToDouble(GetValue(n->Left));
    		double rightvalue = StringToDouble(GetValue(n->Right));
    		std::string finalvalue;
    
    		if (n->Data == "+")
    		{
    			finalvalue = DoubleToString(leftvalue + rightvalue);
    		}
    		else if (n->Data == "-")
    		{
    			finalvalue = DoubleToString(leftvalue - rightvalue);
    		}
    		else if (n->Data == "*")
    		{
    			finalvalue = DoubleToString(leftvalue * rightvalue);
    		}
    		else if (n->Data == "/")
    		{
    			finalvalue = DoubleToString(leftvalue / rightvalue);
    		}
    		else if (n->Data == "MOD")
    		{
    			finalvalue = DoubleToString(int(leftvalue) % int(rightvalue));
    		}
    		else if (n->Data == "^")
    		{
    			finalvalue = DoubleToString(pow(leftvalue, rightvalue));
    		}
    		return finalvalue;
    
    	}
    }

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    I recommend you first write a context free grammar for the expressions you want to accept. After you have your grammar, you can usually turn it into a recursive descent parser fairly easily.

    Example 2 will cover quite a bit of your grammar.

    http://en.wikipedia.org/wiki/Context-free_grammar

    You may also want to read

    http://en.wikipedia.org/wiki/Recursive_descent_parser
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM