Issue with: Recursion/function call/old variable data

Srlancelot39 · **Posted:** Mon Jun 02, 2014 10:52 am

I have this Boolean expression truth table solver that I'm making, and it is working relatively well so far (haven't started the bracket management code yet though *insert 'scared' Emoticon here*) except for the fact that the solution isn't being sent to its column correctly.

For example (as you will see if/when you run the code):
If you enter A+B+C+D as the expression, the recursion function will make a copy of it and solve it (all the way down to 0+0 and then 0 in the first case since the first row of the truth table has all inputs' values set to 0). The function notices that the string (the copy of the expression) is only 1 character long (and therefore solved), and will return the copy of the expression as the value to be displayed.

c:

if (strlen(copyofexpression) > 1)//recurse if there is more to solve
{
Recursion(copyofexpression);
return copyofexpression;
}
else
{
return copyofexpression;
}

The issue begins to arise here:
When the recursion function completes, it returns the copy of the expression. Since the function was last called inside itself, the compiler is sent back to that call. At this point, for some reason, the value of the variable holding the copy of the expression is changed from '0' to '0+0', and this is then passed to the printf in the function that draws the truth table...and for some reason, it doesn't even print '0+0', it prints a random character.

...wtf? lol

c:

#include <stdio.h>
#include <conio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>

char * InputFind(char IF_expression[101]);
char * ReorderInputs();
char AND(char ANDinput1, char ANDinput2);
char OR(char ORinput1, char ORinput2);
char NOT(char NOTinput);
char XOR(char XORinput1, char XORinput2);
void TruthTable(char TT_expression[101]);
char * Recursion(char R_expression[101]);
int RetrieveState(char RSinput);

char inputnames[5] = { NULL };//a list of all input names (in original order)
int inputstates[5];//holds binary state of each input
char reorderedinputnames[5] = { NULL };//a list of all input names (in alphabetical order)

int main()
{
char expression[101] = { NULL };
printf("Enter a boolean expression:\n(Maximum 100 characters, maximum 4 inputs, use capital letters)\n");
do
{
printf("\nX=");
scanf("%s", &expression);
if (strlen(expression) > 100)
{
printf("\nError: Expression is too long.\n");
}
} while (strlen(expression) > 100);
expression[strlen(expression) + 1] = '\0';
strcpy(inputnames, InputFind(expression));//copy "InputFind" onto "inputnames"
if (strcmp(inputnames, "Error") == 0)
{
printf("\nError: Expression contains more than 4 inputs.\nProgram must now terminate.\n\nPress any key to continue...");
getch();
return 0;
}
printf("\nFound %d inputs: %s", strlen(inputnames), inputnames);
strcpy(reorderedinputnames, ReorderInputs(inputnames));//copy "ReorderInputs" ("ordered") onto "reorderedinputnames"
printf(" ==> Re-ordered: %s", reorderedinputnames);
TruthTable(expression);
getch();
}

char * InputFind(char IF_expression[101])
{
char found[5] = { NULL };
int enterfound = 0;
bool addinput = true;
for (int expressionposition = 0; expressionposition <= strlen(IF_expression); expressionposition++)//scans "IF_expression"
{
if ((IF_expression[expressionposition] >= 'A' && IF_expression[expressionposition] <= 'Z'))//checks to see if an input is at current position
{
for (int foundposition = 0; foundposition <= strlen(found); foundposition++)//scans string of found input names ("found")
{
if (IF_expression[expressionposition] == found[foundposition])//checks to see if the input has already been found
{
addinput = false;//set to false so input will not be added to string of found input names
break;//exit loop (to avoid wasting iterations)
}
}
if (addinput == true)//checks to see if newly found input should be added to string of found input names
{
if (strlen(found) < 4)
{
found[enterfound] = IF_expression[expressionposition];//adds newly found input to string of found input names
found[enterfound + 1] = '\0';
enterfound = enterfound + 1;
}
else
{
return "Error";
}
}
addinput = true;//reset to true
}
}
return found;
}

char * ReorderInputs()
{
char ordered[5] = { NULL };
char temp = NULL;
for (int iteration = 1; iteration <= strlen(inputnames); iteration++)//repeats reordering process for the number of input names found
{
for (int inputnamesposition = 0; inputnamesposition <= strlen(inputnames); inputnamesposition++)//scans "RIinputnames"
{
if ((inputnames[inputnamesposition] > inputnames[inputnamesposition + 1]) && (inputnames[inputnamesposition + 1] >= 'A' && inputnames[inputnamesposition + 1] <= 'Z'))//checks to see if ASCII value of input is greater than that of the input to the right of it
{
temp = inputnames[inputnamesposition];//store left input's value in temp
inputnames[inputnamesposition] = inputnames[inputnamesposition + 1];//assign value of right input to left input
inputnames[inputnamesposition + 1] = temp;//assign left input's stored value to right input
}
}
}
strcpy(ordered, inputnames);
return ordered;
}

char NOT(char NOTinput)
{
int value = RetrieveState(NOTinput);
if (value == 1)
{
return '0';
}
else
{
return '1';
}
}

char AND(char ANDinput1, char ANDinput2)
{
int value1;
int value2;
if (RetrieveState(ANDinput1) == '1')
{
value1 = 1;
}
else
{
value1 = 0;
}
if (RetrieveState(ANDinput2) == '1')
{
value2 = 1;
}
else
{
value2 = 0;
}
if (value1 * value2 == 1)
{
return '1';
}
else
{
return '0';
}
}

char OR(char ORinput1, char ORinput2)
{
int value1;
int value2;
if (RetrieveState(ORinput1) == '1')
{
value1 = 1;
}
else
{
value1 = 0;
}
if (RetrieveState(ORinput2) == '1')
{
value2 = 1;
}
else
{
value2 = 0;
}
if ((value1 + value2) >= 1)
{
return '1';
}
else
{
return '0';
}
}

char XOR(char XORinput1, char XORinput2)
{
int value1 = RetrieveState(XORinput1);
int value2 = RetrieveState(XORinput2);
if ((value1 + value2) == 1)
{
return '1';
}
else
{
return '0';
}
}

void TruthTable(char TT_expression[101])
{
printf("\n");
for (int names = 0; names < strlen(reorderedinputnames); names++)//draw inputs
{
printf("%c ", reorderedinputnames[names]);
}
printf("X");
for (int row = 1; row < pow(2, strlen(reorderedinputnames)) + 1; row++)//draw table
{
printf("\n");
if (strlen(reorderedinputnames) > 3)//if more than 3 inputs
{
if (row > 8 && row < 17)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
if (strlen(reorderedinputnames) > 2)//if more than 2 inputs
{
if ((row > 4 && row < 9) || (row > 12 && row < 17))
{
printf("1 ");

}
else
{
printf("0 ");
}
}
if (strlen(reorderedinputnames) > 1)//if more than 1 input
{
if (row == 3 || row == 4 || row == 7 || row == 8 || row == 11 || row == 12 || row == 15 || row == 16)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
if (strlen(reorderedinputnames) > 0)//if any inputs
{
if (row % 2 == 0)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
printf("%s", Recursion(TT_expression));
}
}

char * Recursion(char R_expression[101])
{
char copyofexpression[101];
strcpy(copyofexpression, R_expression);
for (int scan = 0; scan < strlen(copyofexpression); scan++)//check for operators
{
if (copyofexpression[scan] == '(')
{
//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] == '!')
{
NOT(copyofexpression[scan + 1]);
}
else if (copyofexpression[scan] == '*')
{
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 - 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;
}
}
}
}
if (strlen(copyofexpression) > 1)//recurse if there is more to solve
{
Recursion(copyofexpression);
return copyofexpression;
}
else
{
return copyofexpression;
}
}

int RetrieveState(char RSinput)
{
if (RSinput == '0' || RSinput == '1')
{
return RSinput;
}
else
{
for (int index = 0; index < strlen(inputnames); index++)//scan "inputnames"
{
if (RSinput == inputnames[index])//if "RSinput" is equal to the input at the current location in "inputnames"
{
return inputstates[index];//return the state at the current location in "inputstates"
}
}
}
}

I am using Visual Studio Professional 2013.

Btw, anyone know how to change code colouring in the editor? i.e., make it look how it appears in these forums?

Thanks!

Tony · **Posted:** Mon Jun 02, 2014 11:31 am

code:

char * Recursion(char R_expression[101])
{
char copyofexpression[101];
strcpy(copyofexpression, R_expression);
...
return copyofexpression;
...
}

It looks like you are creating copyofexpression on the stack, returning a pointer to the variable, but the variable is destroyed once the function exits. Still, the pointer points to some address in the memory, and that could be attempted to be read as whatever type you want. No guarantees as to what's going to be there though.

Quote:

...it prints a random character...

You can either return the full value, or allocate the space on the heap (malloc), which you would have to clean up on your own.

Srlancelot39 · **Posted:** Mon Jun 02, 2014 12:12 pm

That is most likely the issue. Could this be solved by changing the storage type? I.e. static, global, etc?
I did that with a bunch of other variables and it really cleaned up/simplified my functions...

EDIT: Can you explain more about the pointer being passed to the variable? I wasn't even aware that there was a pointer involved lol, and what variable is it being passed to (just to be clear)?

Tony · **Posted:** Mon Jun 02, 2014 1:32 pm

Srlancelot39 @ Mon Jun 02, 2014 12:12 pm wrote:

I wasn't even aware that there was a pointer involved

What's the return type of:

code:

char * Recursion(char R_expression[101]) {}

Answer: http://cdecl.ridiculousfish.com/?q=char+*+foo%28%29%3B

Srlancelot39 @ Mon Jun 02, 2014 12:12 pm wrote:

what variable is it being passed to (just to be clear)?

The returned value is being used at least in

code:

printf("%s", Recursion(TT_expression));

But you also make recursive calls

code:

Recursion(copyofexpression);

which will return (what's the state of the stack at that point?)

https://en.wikipedia.org/wiki/Function_stack#Unwinding

Quote:

Returning from the called function will pop the top frame off of the stack

Srlancelot39 · **Posted:** Mon Jun 02, 2014 4:02 pm

Haha, oops! I thought char * <function> would define a function that returns a string.

And okay, I was aware that it was being passed to/through the function calls, I just wasn't thinking of them as variables when you mentioned it and thus was curious Razz

Thanks! I like the way you answer; helpful, yet not simply tossing out a solution.

I'm gonna go experiment/read on returning strings and using storage types...

EDIT: Just remembered that char * <function> is required for strings since strings are pointers to arrays of characters...so what I need to do is get the pointer working correctly, not eliminate it lol

Srlancelot39 · **Posted:** Mon Jun 02, 2014 6:59 pm

Fixed it! As it turns out, there were other issues in addition to the ones you found, but I didn't find them until after fixing the issues you mentioned, so...

Thanks, Tony!

+1 Karma

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members