No one in their right mind would do this recursively...
Here's how to do it recursively...
Take a postfix expression grammar
exp -> term opt_exp op
term -> ( exp opt_unary_ops ) | digits
opt_exp -> empty_sequence | exp
opt_unary_ops -> empty_sequence | + | -
op -> + | - | * | /
Note three things about this grammar
1. the first character of a term is a '(' or a digit.
2. an exp starts with a term (so must start with '(' or a digit)
3. we can satisfy opt_exp by not consuming any input but we actually want to
consume as much of the input string as possible so we take the exp branch of
this rule if we see the start of an expression.
You might want to treat unary ops differently.
/* some untested code... */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
char *
SkipSpaces( char *s )
{
while ( isspace( *s ) )
{
s++;
}
return s;
Quote:
}
long
ApplyUnaryOps( char *ExpIn, char **ExpOut, long Val )
{
do
{
ExpIn = SkipSpaces( ExpIn );
if ( '-' == *ExpIn )
{
Val = -Val;
ExpIn++;
}
if ( '+' == *ExpIn )
ExpIn++;
ExpIn = SkipSpaces( ExpIn );
} while ( '-' == *ExpIn || '+' == *ExpIn );
*ExpOut = ExpIn;
return Val;
Quote:
}
long EvalPostFixExp( char *ExpIn, char **ExpOut, int *IsErr );
int
IsFirstCharOfTerm( char c )
{
return isdigit( c ) || '(' == c;
Quote:
}
long
EvalTerm( char *ExpIn, char **ExpOut, int *IsErr )
{
long Val = 0L;
ExpIn = SkipSpaces( ExpIn );
if ( ! IsFirstCharOfTerm( *ExpIn ) )
{
*IsErr = 1;
*ExpOut = ExpIn;
return 0L;
}
if ( isdigit( *ExpIn ) )
Val = strtol( ExpIn, ExpOut, 10 );
else
{
char *NextExp;
assert( '(' == *ExpIn );
Val = EvalPostFixExp( ++ExpIn, &NextExp, IsErr );
if ( *IsErr )
return 0;
Val = ApplyUnaryOps( NextExp, &NextExp, Val );
NextExp = SkipSpaces( NextExp );
if ( ')' == *NextExp )
*ExpOut = ++NextExp;
else
*IsErr = 1;
}
return Val;
Quote:
}
long
EvalPostFixExp( char *ExpIn, char **ExpOut, int *IsErr )
{
long Val, Val2;
char *ExpAfterVal2, *NextExp;
Val = EvalTerm( ExpIn, &NextExp, IsErr );
for ( ; ; )
{
NextExp = SkipSpaces( NextExp );
if ( *IsErr || ! IsFirstCharOfTerm( *NextExp ) )
{
*ExpOut = NextExp;
return Val;
}
Val2 = EvalPostFixExp( NextExp, &ExpAfterVal2, IsErr );
if ( *IsErr )
{
*ExpOut = ExpAfterVal2;
*IsErr = 1;
return 0;
}
ExpAfterVal2 = SkipSpaces( ExpAfterVal2 );
switch ( *ExpAfterVal2 )
{
case '+': Val += Val2; break;
case '-': Val -= Val2; break;
case '*': Val *= Val2; break;
case '/': if ( 0 == Val2 )
{
*ExpOut = ExpAfterVal2;
*IsErr = 1;
return 0;
}
Val /= Val2;
break;
default: *ExpOut = ExpAfterVal2;
*IsErr = 1;
return 0;
}
NextExp = ExpAfterVal2+1;
}
*ExpOut = NextExp;
return Val;
Quote:
}
int
main()
{
for ( ; ; )
{
long Val;
char *ExpOut, Exp[1000];
int IsErr;
if ( NULL == fgets( Exp, 1000, stdin ) )
break;
if ( strncmp( Exp, "quit", 4 ) == 0 )
break;
IsErr = 0;
Val = EvalPostFixExp( Exp, &ExpOut, &IsErr );
if ( ! IsErr && '\0' == *ExpOut )
printf( "%s=%ld\n", Exp, Val );
else
{
int ErrPos = strlen( Exp ) - strlen( ExpOut );
printf( "\n%s=?\n", Exp, Val );
printf( "%*.*s", ErrPos, ErrPos, "" );
printf( "%s (%s)\n", "^ERROR here!", ExpOut );
}
}
return 0;
Quote:
}
Quote:
> > >> > how can i do it???
> > >> > i have a recursive function that eval a prefix expr.. but postfix
is
> > >> > impossible for me..
> > >> Well, then, maybe you should consider another career.
> > >> It is *really* easy to do this. Do you know what a "stack" is?
> > >Ehm.. are you joking?
> > >If not i would see the code.
> > I agree with Douglas this is really easy with a stack.
> What do you mean by stack? a stack implemented linked list? or the stack
of
> the machine?
> with a stack it's easy but i need a *recursive function* so i must use the
> stack of the computer..
> The basic scheme
> > is as follows.
> > 1. Tokenize the expression, something like the following as an example
> > 1 2 + 3 *
> > Split this into separate tokens based on the spaces.
> > 2. Take each token from left to right and
> > a) if its a number push it on to the stack
> > b) if its an operation pop appropiate values from the stack, do the
> > operation and push the result.
> > 3. Return what ever is left on the stack.
> > Should take very little code to actually write.
> Yes, with a stack it's easy, but without it?
> > --
> > --
> --
--