Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Recursion MALfunction issue (...lol)
Index -> Programming, C -> C Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Srlancelot39




PostPosted: Thu Jun 19, 2014 11:58 am   Post subject: Recursion MALfunction issue (...lol)

Ok, I'm really getting tired of denying myself online help with this issue, so here we go!

I have a recursive function in a program I made that solves Boolean expressions (prints the truth table). I have posted the function previously in another thread, but the issue I had then is different from this.

The problem I am having only occurs with certain expressions and after a certain size.
For example, here is the main occurrence (and also the first one I noticed):
The expression !A*!B*!C*!D+A*B*C*D will output all 0s in the output column of the truth table...which is incorrect.

However, the expression !A*!B*!C+A*B*C will display all correct output...actually that's not true anymore - it used to work, but now it doesn't seem to...is this error contagious or something? -.-

What DOES currently work (in terms of this style of expression) is !A*!B+A*B.

In general, the program works correctly aside from certain expressions like those aforementioned, so if you entered A*B+C*D or A+B*C+D or A*B*C*D or !A*!B*!C*!D it would display the correct output.

What I do know about the issue is this:
(Assume input = !A*!B*!C*!D+A*B*C*D)
By stepping through the code, I have noticed that at some point it decides to solve the addition before all the multiplication is done. This results in a 0 being multiplied through the rest of the expression every time, and thus resulting in an output of 0.

(Finally,) Here is the relevant code:
c:

char * Recursion(char R_expression[101])
{
        strcpy(copyofexpression, R_expression);
        if (strlen(copyofexpression) > 1)//if expression is 2 or more characters
        {
                for (int operator = 0; operator <= 3; operator++)//select operator
                {
                        for (int scan = 0; scan < strlen(copyofexpression); scan++)//check for operators
                        {
                                if ((copyofexpression[scan] == '(') && (copyofexpression[scan] == OPERATORS[operator]))
                                {
                                        //repeat 'for' process, searching again for opening brackets until closing bracket is found.  If no further opening brackets are found, search for NOT, AND, OR...
                                }
                                else if ((copyofexpression[scan] == '!') && (copyofexpression[scan] == OPERATORS[operator]))
                                {
                                        copyofexpression[scan] = NOT(copyofexpression[scan + 1]);
                                        for (int shift = scan; shift < strlen(copyofexpression); shift++)
                                        {
                                                copyofexpression[shift + 1] = copyofexpression[shift + 2];
                                                if (shift == strlen(copyofexpression))//if removing end of string
                                                {
                                                        copyofexpression[strlen(copyofexpression) - 1] = '\0';
                                                }
                                        }
                                }
                                else if ((copyofexpression[scan] == '*') && (copyofexpression[scan] == OPERATORS[operator]))
                                {
                                        copyofexpression[scan - 1] = AND(copyofexpression[scan - 1], copyofexpression[scan + 1]);
                                        for (int shift = scan; shift < strlen(copyofexpression); shift++)
                                        {
                                                copyofexpression[shift] = copyofexpression[shift + 2];
                                                if (shift == strlen(copyofexpression) - 1)//if removing end of string
                                                {
                                                        copyofexpression[strlen(copyofexpression) - 3] = '\0';
                                                        copyofexpression[strlen(copyofexpression) - 2] = NULL;
                                                }
                                        }
                                }
                                else if ((copyofexpression[scan] == '+') && (copyofexpression[scan] == OPERATORS[operator]))
                                {
                                        copyofexpression[scan - 1] = OR(copyofexpression[scan - 1], copyofexpression[scan + 1]);
                                        for (int shift = scan; shift < strlen(copyofexpression); shift++)
                                        {
                                                copyofexpression[shift] = copyofexpression[shift + 2];
                                                if (shift == strlen(copyofexpression) - 1)//if removing end of string
                                                {
                                                        copyofexpression[strlen(copyofexpression) - 3] = '\0';
                                                        copyofexpression[strlen(copyofexpression) - 2] = NULL;
                                                }
                                        }
                                }
                        }
                }
        }
        else if (strlen(copyofexpression) == 1 && copyofexpression[0] >= 'A' && copyofexpression[0] <= 'Z')
        {
                if (RetrieveState(copyofexpression[0]) == 1)
                {
                        copyofexpression[0] = '1';
                }
                else
                {
                        copyofexpression[0] = '0';
                }
        }
        if (strlen(copyofexpression) > 1)//recurse if there is more to solve
        {
                Recursion(copyofexpression);
                return copyofexpression;
        }
        else
        {
                return copyofexpression;
        }
}


I have a strong feeling that my if logic is flawed, causing my order of operations to screw up, but even after much thinking, I still can't think of what it should be.

If you need to see more of the code, just say so Smile (I'm just trying to release as little of the code as possible)
Sponsor
Sponsor
Sponsor
sponsor
DemonWasp




PostPosted: Thu Jun 19, 2014 12:07 pm   Post subject: RE:Recursion MALfunction issue (...lol)

First, this isn't a recursive function (it never calls itself).

Secondly, your problem probably has to do with referring to strlen(copyofexpression), but then putting '\0' and NULLs into that string. Look up how strlen() works and it should be pretty clear why replacing characters with '\0' will cause you problems.

Third, you have some seriously screwed up logic. For example, your first if condition tests whether a single character in the expression is equal to both '(' and one of your operators (I'm assuming +, -, *, /).
Srlancelot39




PostPosted: Thu Jun 19, 2014 12:11 pm   Post subject: Re: Recursion MALfunction issue (...lol)

c:

Recursion(copyofexpression);

The function does call itself.

Replacing characters with \0 is messy indeed, but it is working correctly as far as I have seen. As I said in my original post though, an issue I have witnessed is incorrect order of operations occurring in some cases.

This is the string of operators:
c:

const char OPERATORS[] = { '(', '!', '*', '+' };


There is no division or subtraction because it is solving Boolean expressions.

So the if you mentioned is actually checking to see if: '(' = current operator being checked for = character in expression being examined.
jr5000pwp




PostPosted: Thu Jun 19, 2014 8:53 pm   Post subject: RE:Recursion MALfunction issue (...lol)

I think there may be a flaw in your iteration logic. Say you have A*B*C*D+A*B*C*D, you go through, first step you AND A and B then you get E*C*D+A*B*C*D, E being the result. Your scan value is going to advance one and now you're checking C for an operator. You then get to the next * and your output is now E*F+A*B*C*D. You do this for the rest of the sequence and you get E*F+G*H, then you continue onto the next operator, +, this will add F and G, which is not what you want. I think you can get away with just doing scan-- after doing a * or +, but I may be wrong.
Srlancelot39




PostPosted: Thu Jun 19, 2014 10:51 pm   Post subject: Re: Recursion MALfunction issue (...lol)

Yeah I think you're right about the iteration. Specifically though, I think it has to do with my combination and ordering of conditions (ifs); I think they need to be changed to properly follow order of operations in all situations. I stress "in all situations" because the function works fine in most cases, but in others (like the ones mentioned) it solves addition (ORs) when there is still multiplication (ANDs) to be solved. OR should only be solved before AND when the OR is in brackets, and I don't even have brackets implemented yet lol. (Maybe I should just pretend that my program is a VHDL simulator, since VHDL does not follow order of operations...but then I'd REALLY need to implement brackets...aggh, you can't win lol)

Back to the iteration, yeah that might have something to do with it since shorter expressions of the same style work correctly. E.g. !A*!B+A*B works, but !A*!B*!C+A*B*C does not...

Oh and does anyone know of a debugger I can use aside from the one in Visual Studio? Or does VS have a really good one and I'm just not seeing it? So far I've just been stepping through the code and adding watches (that don't always work correctly? Sometimes it'll put a red X next to them, and other times it won't...).

Thanks!

EDIT:
jr5000pwp @ Thu Jun 19, 2014 8:53 pm wrote:
Say you have A*B*C*D+A*B*C*D


It solves that expression correctly actually Razz It's just when you have all NOTs on only side. I tested !A*!B*!C*!D+!A*!B*!C*!D and it solves that correctly too...Eh Hmmm...
jr5000pwp




PostPosted: Fri Jun 20, 2014 10:23 am   Post subject: Re: Recursion MALfunction issue (...lol)

C:
for (int shift = scan; shift < strlen(copyofexpression); shift++)
{
    copyofexpression[shift + 1] = copyofexpression[shift + 2];
    if (shift == strlen(copyofexpression))//if removing end of string
    {
        copyofexpression[strlen(copyofexpression) - 1] = '\0';
    }
}
Your if statement will never get hit in this case, although this one might not cause too much of a problem. Also, I'm not a C developer, I'm a C# developer, but I think you have some bounds issues with this
C:
for (int shift = scan; shift < strlen(copyofexpression); shift++)
{
    copyofexpression[shift] = copyofexpression[shift + 2];
    if (shift == strlen(copyofexpression) - 1)//if removing end of string
    {
        copyofexpression[strlen(copyofexpression) - 3] = '\0';
        copyofexpression[strlen(copyofexpression) - 2] = NULL;
    }
}
When shift == strlen(copyofexpression) - 2 and above, you're accessing outside the array bounds. strlen(copyofexpression) - 2 + 2 == strlen(copyofexpression) which is out of bounds. I'm not sure how arrays behave in C, but from what I've heard this can be a very bad thing. As for !A*!B*!C+A*B*C, I believe this expression will be evaluated as !A*!B*(!C+A*B)*C which is obviously not correct.
Srlancelot39




PostPosted: Fri Jun 20, 2014 7:43 pm   Post subject: RE:Recursion MALfunction issue (...lol)

I think you're definitely on to something. Also, I put that specific part of the code together pretty quickly without thinking it through very hard (EDIT: ok well tbh I did put some time and thought into it, but I wasn't very confident about it lol).
I might need to just rebuild that part of the code completely, rather than trying to repair it.

The purpose of those code segments is to remove parts of the expression that have been solved, and sew the remaining parts of the expression back together (re-concatenate them). I'm going to try to think of a cleaner algorithm for that, but if you come up with anything, please suggest it here Razz
Display posts from previous:   
   Index -> Programming, C -> C Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 7 Posts ]
Jump to:   


Style:  
Search: