Expression tree for 2 digit inputs

Question

I am trying to make an expression tree that is capable of inserting two digit numbers. Right now, it can only insert digits 0 - 9 because of char's capabilities. My current code works on for postfix expressions, so when I make an expression tree for "+52" it evaluates to 10. If I want to make an expression for 10 * 2, it would not work because my code sees it as 3 digits and an operator.

Here's my code:

/*
 * C++ Program to Implement Expression Tree
 */
#include <iostream>
#include <cstdlib>
#include <cstdio>     
#include <cstring> 
using namespace std;

/** class TreeNode **/
class TreeNode
{       
    public:
        char data;
        TreeNode *left, *right;
        /** constructor **/
        TreeNode(char data)
        {
            this->data = data;
            this->left = NULL;
            this->right = NULL;
        }
}; 

/** class StackNode **/
class StackNode
{    
    public:
        TreeNode *treeNode;
        StackNode *next;
        /** constructor **/ 
        StackNode(TreeNode *treeNode)
        {
            this->treeNode = treeNode;
            next = NULL;
        }
};


class ExpressionTree
{
    private:
        StackNode *top;
    public:
        /** constructor **/ 
        ExpressionTree()
        {
            top = NULL;
        }

        /** function to clear tree **/
        void clear()
        {
            top = NULL;
        }

        /** function to push a node **/

        void push(TreeNode *ptr)
        {
            if (top == NULL)
                top = new StackNode(ptr);
            else
            {
                StackNode *nptr = new StackNode(ptr);
                nptr->next = top;
                top = nptr;
            }
        }

        /** function to pop a node **/
        TreeNode *pop()
        {
            if (top == NULL)
            {
                cout<<"Underflow"<<endl;
            }
            else
            {
                TreeNode *ptr = top->treeNode;
                top = top->next;
                return ptr;
            }
        }

        /** function to get top node **/
        TreeNode *peek()
        {
            return top->treeNode;
        }


        /** function to insert character **/
        void insert(char val)
        {
            if (isDigit(val))
            {
                TreeNode *nptr = new TreeNode(val);
                push(nptr);
            }
            else if (isOperator(val))
            {
                TreeNode *nptr = new TreeNode(val);
                nptr->left = pop();
                nptr->right = pop();
                push(nptr);
            }
            else
            {
                cout<<"Invalid Expression"<<endl;
                return;
            }
        }

        /** function to check if digit **/
        bool isDigit(char ch)
        {
            return ch >= '0' && ch <= '9';
        }

        /** function to check if operator **/
        bool isOperator(char ch)
        {
            return ch == '+' || ch == '-' || ch == '*' || ch == '/';
        }


        /** function to convert character to digit **/
        int toDigit(char ch)
        {
            return ch - '0';
        }

        /** function to build tree from input */

        void buildTree(string eqn)
        {
            for (int i = eqn.length() - 1; i >= 0; i--)
                insert(eqn[i]);
        }

        /** function to evaluate tree */
        double evaluate()
        {
            return evaluate(peek());
        }

        /** function to evaluate tree */
        double evaluate(TreeNode *ptr)
        {
            if (ptr->left == NULL && ptr->right == NULL)
                return toDigit(ptr->data);
            else
            {
                double result = 0.0;
                double left = evaluate(ptr->left);
                double right = evaluate(ptr->right);
                char op = ptr->data;
                switch (op)
                {
                case '+': 
                    result = left + right; 
                    break;
                case '-': 
                    result = left - right; 
                    break;
                case '*': 
                    result = left * right; 
                    break;
                case '/': 
                    result = left / right; 
                    break;
                default: 
                    result = left + right; 
                    break;
                }
                return result;
            }
        }


};



/** Main Contains menu **/
int main()
{
    string s;
    cout<<"Expression Tree Test"<<endl;
    ExpressionTree et;
    et.buildTree("*52");
    cout<<"\n\nEvaluated Result : "<<et.evaluate();
}

How do I make it so that the code is capable of handling and evaluating two digit numbers?

Answer 1

First of all, '+ 5 2' is called prefix, not postfix notation. I am not sure if you want to convert your code to handle infix expressions(5+2), which would require you to rewrite the entire thing pretty much, or prefix expressions with multiple digits (+ 10 5), in either case you probably want to account for whitespace in the input string.

You should change Treenode.data to be an int instead of char, as realistically you expect "+ 10 5" to be parsed as three treeNodes in total, one of them holding "10".

The usual way of doing this is to first split your input string into tokens before passing a collection of tokens to buildTree. The input string "+ 10 5" has to first become a vector/array containing strings "+", "10", "5". Then later when you pass this collection to buildTree, each element will become a new TreeNode.

Other than that, looking at your code StackNode class seems redundant; you should be able to do everything you want with only having TreeNode.