Parse tree doesn't work

Question

I want to build simple parse tree/but it's not working. I think that strlen is returning the wrong result.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

int min(int a ,int b){ return (a>b)?b:a;}

class Node
{
    Node* left;
    Node* right;
    char operation;

public:
    float res;

    Node(char* str)
    {
        char* ch = NULL;
        ch = strrchr2(str);
        if (ch==NULL)
        {
            if(str[0]=='(')
            {
                str = &str[1]; 
                int k = strlen(str);
                char *tmp = new char[k-1];

                strncpy(tmp,str,k-1);
                ch = strrchr2(tmp);

                div(tmp,ch);
            }
            else
                res = atof(str);                
        }
        else
        {
            div(str,ch);
        }
    }

    void div(char* str,char* ch)
    {
            //getting opertion
            strncpy(&operation,ch,1);

            //getting position of operation
            int pos = strlen(str)-strlen(ch);

            //right node creation
            ch = &ch[1];
            right = new Node(ch);

            //left node creation
            char* tmp = new char[pos];
            strncpy(tmp,str,pos);
            left = new Node(tmp);

            //applying opertion to to node's results
            switch( operation )
            {
                case '/':this->res = left->res/right->res;break;
                case '*':this->res = left->res*right->res;break;
                case '+':this->res = left->res+right->res;break;
                case '-':this->res = left->res-right->res;break;
                default:break;
            };
    }

    char* strrchr2(char* s)
    {
        char* str = new char[strlen(s)];
        strcpy(str,s);
        int i = search(str);
        if(i==-1) return NULL;
            else
        if(str[i]=='+' || str[i]=='-') return &str[i];
            else if (str[i] == '*' || str[i]=='/')
            {
                char c = str[i+1];
                if(i+1<strlen(str)-1 && search(&c)!=-1) return strrchr2(&c);
                else return &str[i];
            }
    }

    int search(char* str)
    {
        int cnt1 = 0;
        int cnt2 = 0;
        for(int i=0;i<strlen(str);i++)
        {
            if (str[i]=='(') cnt1++;
            else if (str[i]==')') cnt2++;
            if (cnt1!=0)
            {
               if(cnt1==cnt2)
               {
                  int m = strlen(str);
                  return ((i+1)!=m?i+1:-1);
               }
            }
            else
            {
                if (str[i]=='-' || str[i]=='+' || str[i]=='*' || str[i]=='/') return i;
            }
        }
        char* ch = NULL;
        ch = strchr(str,'-');
        if(ch==NULL) ch = strchr(str,'+');
        if(ch==NULL) ch = strchr(str,'*');
        if(ch==NULL) ch = strchr(str,'/');
        if(ch==NULL)return -1;
        else return strlen(str)-strlen(ch);
    }
};

int main()
{
    char* expr = "(1/2)-(1/2)";
    Node* n = new Node(expr);
    printf("%s = %.3f",expr,n->res);



    _getch();
}

Answer 1

Here's what you do.

You make sure you are using a good IDE with an integrated debugger. It is absolutely vital that you can step through the code and look at variables. It is possible for experts to debug code without these luxuries, but requires a very significant amount of expertise.

So you need a debugger. If you're on Windows, you could get Visual Studio 2010 Express for free. Or you might already have a debugger.

What you do next is you step through the code, line by line, and ensure that it does exactly what it should to at every step. It's tedious, but that's how it goes.

"This code doesn't work" doesn't cut it. The only thing people on StackOverflow could do for you (short of spotting obvious errors based on luck) is load the code into their own debugger and step through it for you. But you really need to learn to do it yourself.

P.S. Library functions and compilers essentially always work. If you think you found a bug in one, you almost certainly haven't. If you still think so, try to reproduce that bug with just a few lines of code. If there really is a bug then it will almost always be reducible down to a 5-line program. If you can't reduce it to a very short program, then it's almost certainly a bug in your code, and if it isn't then you'll know that without asking on StackOverflow.

Answer 2

It seems like you are doing C with class more than C++. Try using std::string insted of char *. This way you won't have any trouble with strlen (if strlen is really the problem) because string has a size() function and it is garantied to work very well. Most of all you'll be able to use many features that you are trying to re-code there.

More informations about strings : http://www.cplusplus.com/reference/string/string/

M.Dijsktra also created an algorithm to parse mathematical expressions and output an AST (Abstract Syntax Tree). It will allow you to deal with more complex expression. It's called the 'shunting yard algorithm'. Here it is on wikipedia : http://en.wikipedia.org/wiki/Shunting-yard_algorithm

I thought you might want to know what's already been done . :)