need Recursion help

[degamer106]

This problem is asking me to convert an infix expression to a postfix expression using recursion. I did the exact same problem using stacks (w/o recursion), which was much easier, but on this one, I get stumped constantly when I try to come up with a line of code to call the function(itself) again. So far, what I've come up with is not really a true recursion function as it does not return a value =\ Thanks for any tips you guys can give. (And sorry if the code in the brackets is too compact).

fyi: The format of the input has to be something like (5*9) or it won't work.

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

#define LEN 100

static char input[LEN], hold[LEN];
static int i, j, cnt;

void eval();

int main(void)
{
	
	puts("Enter an infix expression:");
	fgets(input, LEN, stdin);

	eval();
	return 0;
}

void eval()
{
	int x = 0;
	if (input[i] == '(') i++; 
	if (input[i] == ')')
	{ 
		printf("%c", hold[--j]); 
		i++;
	}
	if (input[i] == '*' || input[i] == '+')
	{ hold[j++] = input[i]; i++; }
	while (isdigit(input[i]))
	{
		x = 10*x + (input[i++]-'0');
		printf("%d", x);
	}
	eval();
}

[WolfPack]

-bah- Irrelevant post. Will look further.

Edit.
Looks okay at first glance.

[Rashakil Fol]

You're right; this isn't really recursion; you're just making a cute loop (and never returning :-)).

Once you get this working properly, the stack datastructure you are currently using will be replaced by the chain of recursive calls (which in a way, can be thought of a datastructure, too).

Here is how I recommend you think: "Reading an expression either requries reading an individual number, or, it requires reading one expression, reading an operator, and reading another expression." See the recursion in the way I've defined 'reading an expression'?

[degamer106]

heheee yes your definition calls itself.

i'm gonna give this another shot ;p

[degamer106]

OK..I went through a couple of C books and some webpages to do some simple excersizes on recursion and I understand it a little better now. SoOoOo, here's my program which is only slightly modified from the original I posted 2 days ago. Any suggestions you guys can give would be helpful b/c I know that this is not a real recursion =\

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

#define LEN 100

static char input[LEN];
static int i;

void eval();

int main(void)
{
	puts("Enter an infix expression:");
	fgets(input, LEN, stdin);

	eval();

	return 0;
}

void eval()
{
	char hold;

	if (input[i] == '(') i++;
	if (isdigit(input[i]))
	{ printf("%c", input[i]); i++;}
	if (input[i] == '*' || input[i] == '+')
	{ 
		hold = input[i];
		i++; eval(); 
		printf("%c", hold);
	}
	if (input[i] == ')') 
	{ i++; return; }
	eval();
}

[dude543]

first of all you did'nt initalize i !!!

The a close look at this program.

int product(int  n);
int main(void)
{
char   buf[100];
int    num;
printf("Enter number for porduct : ");
fgets(buf, sizeof(buf), stdin);
num = atoi(buf);
num = product(num);
printf("num = %d\n", num);
printf("Press enter to end ....\n");
getchar();
return(0);
}
/* There are 3 steps in writing a recursion 
   1) assume it knows how to calcluate the 
      previsous value.
   2) write the current value by the 
      previsous step.
   3) Make a stop conditon.
*/
int product(int  n)
{
int  tmp;
 
 
/* step 3 */
if ( n < 2 )
   return(1);
 
 
/* step 1 */
tmp = product(n-1);
 
/* step 2 */
return(n * tmp);

}

[degamer106]

i is automatically initialized to 0 if its external. Also that looks like the factorial program that's pretty much everywhere =\

i is automatically initialized to 0 if its external. Also that looks like the factorial program that's pretty much everywhere =\

No offence, but if you're new to recursion, isn't it asking a bit much to use it to make an infix to postfix calculator?

But if you're dead set on doing this, essentially "the stack datastructure you are currently using will be replaced by the chain of recursive calls"

So, you need to understand exactly what your stack was doing before in order to replicate the same functionality using recursion.

[Lerner]

Here's my initial thoughts on the process:

The input is a string representing the infix notation of the expression and the return value will be a string representing the outfix notation of the expression.

The function will be passed the input string and an int representing the index of the current element of the string as parameters.

Each call to the function will find 3 strings--operand1, operator, and operand2. The return string will be built up by copying operand1 to the return string and then concatenating a space, operand2, a space, and the operator onto the return string in that order.

If a left parenthesis is found before all three strings have been found the function will advance the index by 1 and call itself using the input string and the current value of the index as parameters.

The terminating condition for the function calls will be finding a right parenthesis or the null char in the input string.

Each return string will be an operand in the calling function.

I haven't actually worked all this out, but it looks like a reasonable place to start from. On the other hand my brain's a bit fried from work today so who knows what pitfall(s) lurk(s) therein. Use at your own risk.

[degamer106]

No offence, but if you're new to recursion, isn't it asking a bit much to use it to make an infix to postfix calculator?

But if you're dead set on doing this, essentially "the stack datastructure you are currently using will be replaced by the chain of recursive calls"

So, you need to understand exactly what your stack was doing before in order to replicate the same functionality using recursion.

Well i'm trying to learn recursion from this Algorithm book (Algorithms in C by Robert Sedgewick) and the author jumps from factorial recursion to a recursive program to evaluate prefix expressions in 3 pages :eek: And because I did stacks already, the author has created, as an excersize, problems involving conversion/calculations using recursion.
Thanks for your guys's help on this. Still wanna know if the function in the program I put up counts as recursin..

And the stack implementation goes something like...
- If its a number, print it
- if its an operator, push the operator onto the stack
- when you encounter a right parenthesis, pop the operator and print it.

So if you have (5*9), you would get 59*.

I think that's basically it.

[Lerner]

If you initialize operand1, operator, and operand2 strings to be empty strings with each function call, then the algorhithm theory I posted should handle it.