a friend of mine was given an assignment to write a function to convert a polish notation to a reverse polish notation, so at the end a string: "sin * - x 4 + 8 3", should be converted to: "x 4 - 8 3 + * sin". There are some constraints, so for example: at the end a pointer should be returned with a memory allocated on the heap, a function prototype should contain only one argument and it should be the original string. I know that using a static variable is a horrible crime against a humanity, but despite that the very best thing we came out with is:
char * prefix2postfix( char ppn_in[] ){
if (ppn_in[0] == '\0') {
return ppn_in;
}
int i = 0;
char *left = "",
*root = "";
while (ppn_in[i] == ' ') i++;
if (is_num(ppn_in[i]) || is_var(ppn_in[i])) {
char tmp[8];
memset(tmp, '\0', 7);
tmp[0] = ' ';
tmp[1] = ppn_in[i];
root = tmp;
left = prefix2postfix(ppn_in + i + 1);
} else if (is_op(ppn_in[i])) {
switch (ppn_in[i]) {
case '+':
root = " +";
break;
case '-':
root = " -";
break;
case '*':
root = " *";
break;
case '/':
root = " /";
break;
}
left = prefix2postfix(ppn_in + i + 1);
} else if (strncmp(ppn_in, "sqrt", 4) == 0) {
root = " sqrt";
left = prefix2postfix(ppn_in + i + 4);
} else if (strncmp(ppn_in, "sqr", 3) == 0) {
root = " sqr";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "sin", 3) == 0) {
root = " sin";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "cos", 3) == 0) {
root = " cos";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "tan", 3) == 0) {
root = " tan";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "log", 3) == 0) {
root = " log";
left = prefix2postfix(ppn_in + i + 3);
}
printf("reached end of the function\n");
static char buff[200];
buff[199] = '\0';
strcpy(buff, left);
strcat(buff, root);
return buff;
}
The problem is (and it is probably not the only one) that i do not know how to end the function properly so that the line printf("reached end of the function\n"); is called only once, in that case I would be able to use malloc because else I would end up with memory leaks. Any suggestions are appreciated!
EDIT
I've tried to come with something on my own, do i end up creating memory leaks? (I know it is very inefficient, but I allocate 200 bytes, copy them to a new buffer and after I used the value I call free)
char * prefix2postfix( char ppn_in[] ){
if (ppn_in[0] == '\0') {
return ppn_in;
}
int i = 0;
char *left = "",
*root = "";
while (ppn_in[i] == ' ') i++;
if (is_num(ppn_in[i]) || is_var(ppn_in[i])) {
char tmp[8];
memset(tmp, '\0', 7);
tmp[0] = ' ';
tmp[1] = ppn_in[i];
root = tmp;
left = prefix2postfix(ppn_in + i + 1);
} else if (is_op(ppn_in[i])) {
switch (ppn_in[i]) {
case '+':
root = " +";
break;
case '-':
root = " -";
break;
case '*':
root = " *";
break;
case '/':
root = " /";
break;
}
left = prefix2postfix(ppn_in + i + 1);
} else if (strncmp(ppn_in, "sqrt", 4) == 0) {
root = " sqrt";
left = prefix2postfix(ppn_in + i + 4);
} else if (strncmp(ppn_in, "sqr", 3) == 0) {
root = " sqr";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "sin", 3) == 0) {
root = " sin";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "cos", 3) == 0) {
root = " cos";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "tan", 3) == 0) {
root = " tan";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "log", 3) == 0) {
root = " log";
left = prefix2postfix(ppn_in + i + 3);
}
char * buff = malloc(200);
buff[199] = '\0';
strcpy(buff, left);
strcat(buff, root);
if(*left != '\0')
free(left);
return buff;
}
Your parsing is not quite doing recursion with two branches, but to answer your question, you need to malloc for the return value each time or the caller would not know when to free. I am keeping the example as C code because I didn't see any C++ in your question.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int is_num( char v ) { return isdigit( v ); }
int is_var( char v ) { return isalpha( v ); }
int is_op( char v ) { return ispunct( v ); }
char * prefix2postfix( char ppn_in[] ){
if (ppn_in[0] == '\0') {
char * ptr = malloc( sizeof( char ) * 1024 );
ptr[0] = '\0';
return ptr;
}
int i = 0;
char tmp[16];
char *left = 0,
*root = "";
while (ppn_in[i] == ' ') i++;
if ( is_var(ppn_in[i])) {
tmp[0] = ' ';
tmp[1] = ppn_in[i];
char *tptr = &tmp[2];
while( is_var(ppn_in[i + 1] ) )
*tptr++ = ppn_in[++i];
*tptr = '\0';
root = tmp;
left = prefix2postfix(ppn_in + i + 1);
} else if (is_num(ppn_in[i]) || is_var(ppn_in[i])) {
char tmp[8];
memset(tmp, '\0', 7);
tmp[0] = ' ';
tmp[1] = ppn_in[i];
root = tmp;
left = prefix2postfix(ppn_in + i + 1);
} else if (is_op(ppn_in[i])) {
switch (ppn_in[i]) {
case '+':
root = " +";
break;
case '-':
root = " -";
break;
case '*':
root = " *";
break;
case '/':
root = " /";
break;
}
left = prefix2postfix(ppn_in + i + 1);
} else if (strncmp(ppn_in, "sqrt", 4) == 0) {
root = " sqrt";
left = prefix2postfix(ppn_in + i + 4);
} else if (strncmp(ppn_in, "sqr", 3) == 0) {
root = " sqr";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "sin", 3) == 0) {
root = " sin";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "cos", 3) == 0) {
root = " cos";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "tan", 3) == 0) {
root = " tan";
left = prefix2postfix(ppn_in + i + 3);
} else if (strncmp(ppn_in, "log", 3) == 0) {
root = " log";
left = prefix2postfix(ppn_in + i + 3);
}
printf("reached end of the function '%s' '%s'\n", left ? left : "", root );
if( left )
{
strcat( left, root );
return left;
}
char * buff = malloc( sizeof( char ) * 1024 );
strcpy( buff, root );
return buff;
}
int main( int argc, char ** argv )
{
if( argc == 2 )
{
char * ptr = prefix2postfix( argv[1] );
printf( "Result: %s\n", ptr );
free( ptr );
}
}
To do what you want:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int is_binary_operator( const char * token )
{
return ( ( *token == '+' ) ||
( *token == '*' ) ||
( *token == '-' ) ||
( *token == '/' ) );
}
int is_unary_operator( const char * token )
{
return ( !strcmp( token, "sin" ) ||
!strcmp( token, "cos" ) ||
!strcmp( token, "tan" ) ||
!strcmp( token, "exp" ) ||
!strcmp( token, "log" ) ||
!strcmp( token, "ln" ) ||
!strcmp( token, "sqrt" ) ||
!strcmp( token, "sqr" ) );
}
int reverse_polish_arranger( char ** tokens, size_t cnt, size_t iter/*, size_t depth*/ )
{
/*printf( "%*sPeeking at %s\n", depth << 1, "", tokens[iter] );*/
if( is_binary_operator( tokens[iter] ) )
{
int next_pos = reverse_polish_arranger( tokens, cnt, iter + 1 /*, depth + 1 */);
int end_pos = reverse_polish_arranger( tokens, cnt, next_pos + 1 /*, depth + 1 */);
char * ptr = tokens[iter];
memmove( tokens + iter, tokens + iter + 1, sizeof( char * ) * ( end_pos - iter ) );
tokens[end_pos] = ptr;
return end_pos;
}
else if( is_unary_operator( tokens[iter] ) )
{
int end_pos = reverse_polish_arranger( tokens, cnt, iter + 1 /*, depth + 1*/ );
char * ptr = tokens[iter];
memmove( tokens + iter, tokens + iter + 1, sizeof( char * ) * ( end_pos - iter ) );
tokens[end_pos] = ptr;
return end_pos;
}
else
return iter;
}
char * reverse_polish( const char * expr )
{
size_t index;
size_t push_index = 0;
size_t len = 0;
char * result = 0;
char * buffer = 0;
char ** pointers = 0;
/* Prepare the workspace. */
if( !expr )
return 0;
len = strlen( expr );
if( !( result = malloc( sizeof( char ) * len ) ) )
return 0;
if( !( buffer = malloc( sizeof( char ) * len ) ) )
{
free( result );
return 0;
}
if( !( pointers = malloc( sizeof( char * ) * len ) ) )
{
free( result );
free( buffer );
return 0;
}
strcpy( buffer, expr );
memset( pointers, 0, sizeof( char * ) * len );
/* Cheap tokenize using space a delimiter. */
pointers[push_index++] = buffer;
for( index = 0; index < len; ++index )
if( buffer[index] == ' ' )
buffer[index++] = '\0', pointers[push_index++] = &buffer[index];
/* printf( "Before:\n" );
* for( index = 0; index < push_index; ++index )
* printf( "Token %3d: %s\n", index, pointers[index] );
*/
/* Do the conversion. */
reverse_polish_arranger( pointers, push_index, 0/*, 0*/ );
/*
* printf( "After:\n" );
* for( index = 0; index < push_index; ++index )
* printf( "Token %3d: %s\n", index, pointers[index] );
*/
/* Prepare output buffer. */
result[0] = '\0';
for( index = 0; index < push_index; ++index )
strcat( strcat( result, pointers[index] ), " " );
/* Cleanup temporary workspace */
free( pointers );
free( buffer );
/* Return new string. */
return result;
}
int main( int argc, char ** argv )
{
if( argc == 2 )
{
char * reversed = reverse_polish( argv[1] );
if( reversed )
{
printf( "Reverse: %s\n", reversed );
free( reversed );
}
else
printf( "Failed to reverse: %s\n", argv[1] );
}
return 0;
}
Results:
./a.out "sin * - x 4 + 8 3"
Reverse: x 4 - 8 3 + * sin