Answer to Question #246400 in C for Ram

Question

Convert an infix expression to its equivalent postfix expression.
Note: The code should have the modularity and should include following functions apart from
main():
 getNextToken(): This functions returns the next token in the input infix expression. The
token may be an operator or “(“ or “)” or an operand. The operands can be of multiple
digits. For example the infix expression 1000/(10+240) contains operands 1000, 10, and
240.
 infixToPostfix(): Converts the input infix expression to postfix. This function calls
getNextToken() repeatedly to get the next token until it reaches the end. The token is
then processed depending on whether it is an operand or operator or ( or )

Answer 1

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



#define MAXOP        100  
#define MAXSTACK    100  


typedef int        BOOL;

#ifndef FALSE
#define FALSE    0
#endif

#ifndef TRUE
#define TRUE    1
#endif


typedef enum tagTokenType
{
    EOL, UNKNOWN, VALUE, OPAREN, CPAREN, EXP, UPLUS, UMINUS, MULT, DIV, PLUS, MINUS
}TokenTypeEnum;

typedef struct tagToken
{
    TokenTypeEnum Type;
    char str[54];
    double Value;
}Token;

struct Precedence
{
    int inputSymbol;
    int topOfStack;
} PREC_TABLE [ ] =
{
    { 0, -1 }, {-1, -1}, { 0, 0 },   
    { 100, 0 }, { 0, 99 },           
    { 6, 5 }, {6, 5}, {6, 5},        
    { 3, 4 }, { 3, 4 },              
    { 1, 2 }, { 1, 2 }               
};

int nNextPos = 0;
TokenTypeEnum PreviousTokenType = EOL;

int sp_op = 0;
Token stack_op[MAXSTACK];  


void push_op(Token, char *);
Token pop_op(char *);
Token top_op(char *);
BOOL is_empty_op();

int sp_val = 0;
double stack_val[MAXSTACK]; 


void push_val(double, char *);
double pop_val(char *);
double top_val(char *);
BOOL is_empty_val();

TokenTypeEnum GetNextToken(const char *str, Token *token, BOOL bIsInfix);

double BinaryOperation(double left, double right, char op, char *strError);

double EvalInfix(const char *strExpression, char *strError);


void push_op(Token Tok, char *strError)
{
    strcpy(strError, "");

    if (sp_op < MAXSTACK)
        stack_op[sp_op++] = Tok;
    else
        sprintf(strError, "Error: operators stack is full, cannot add more elements %c\n", Tok.str[0]);
}


Token pop_op(char *strError)
{
    Token tok_temp;

    strcpy(strError, "");

    if (sp_op > 0)
        return stack_op[--sp_op];
    else
    {
        sprintf(strError, "Error: missing operator\n");
        strcpy(tok_temp.str, "");
        tok_temp.Type = UNKNOWN;
        return tok_temp;
    }
}


Token top_op(char *strError)
{
    Token tok_temp;

    strcpy(strError, "");

    if (sp_op >= 0)
        return stack_op[sp_op - 1];
    else
    {
        sprintf(strError, "Error: missing operator\n");
        strcpy(tok_temp.str, "");
        tok_temp.Type = UNKNOWN;
        return tok_temp;
    }
}


BOOL is_empty_op()
{
    if ( sp_op > 0 )
        return FALSE;
    else
        return TRUE;
}


void push_val(double c, char *strError)
{
    strcpy(strError, "");

    if (sp_val < MAXSTACK)
        stack_val[sp_val++] = c;
    else
        sprintf(strError, "Error: values stack is full: cannot add more elements %g\n", c);
}


double pop_val(char *strError)
{
    strcpy(strError, "");

    if (sp_val > 0)
        return stack_val[--sp_val];
    else
    {
        sprintf(strError, "Error: missing operand\n");
        return 0;
    }
}


double top_val(char *strError)
{
    strcpy(strError, "");

    if (sp_val > 0)
        return stack_val[sp_val - 1];
    else
    {
        sprintf(strError, "Error top: values stack is empty\n");
        return 0;
    }
}


BOOL is_empty_val()
{
    if ( sp_val > 0 )
        return FALSE;
    else
        return TRUE;
}

BOOL is_scientific(char strChar)
{
    static BOOL was_scientific = FALSE;

    if (was_scientific)
    {
        was_scientific = FALSE;
        return TRUE;
    }
    else if (strChar == 'e' || strChar == 'E'||
             strChar == 'd' || strChar == 'D')
    {
        was_scientific = TRUE;
        return TRUE;
    }
    else if ( isdigit(strChar) ){
        was_scientific = FALSE;
        return TRUE;
        }
    else
    {
        was_scientific = FALSE;
        return FALSE;
    }
}



TokenTypeEnum GetNextToken(const char *str, Token *token, BOOL bIsInfix)
{
    int i;
    char strToken[MAXOP];

    while ( 1 )
    {
        while ( str[nNextPos++] == ' ' )
            ;
        --nNextPos;

        if ( str[nNextPos] == '\0' )
        {
            token->Type = EOL;
            strcpy(token->str, "\n");
            nNextPos = 0;
            PreviousTokenType = EOL;
            return EOL;
        }
        else if ( is_scientific(str[nNextPos]) )
        {
            i = 0;
            while ( is_scientific(strToken[i++] = str[nNextPos++]) )
                if (strToken[i-1] == 'd' || strToken[i-1] == 'D') strToken[i-1] = 'e';
            if ( str[nNextPos - 1] == '.' )
            {
                while ( is_scientific(strToken[i++] = str[nNextPos++]) )
                if (strToken[i-1] == 'd' || strToken[i-1] == 'D') strToken[i-1] = 'e';
                strToken[i - 1] = '\0';
                --nNextPos;
                token->Type = VALUE;
                strcpy(token->str, strToken);
                token->Value = atof(strToken);
                return VALUE;
            }
            else
            {
                strToken[i - 1] = '\0';
                --nNextPos;
                token->Type = VALUE;
                strcpy(token->str, strToken);
                token->Value = atof(strToken);
                return VALUE;
            }
        }
        else if ( str[nNextPos] == '.' )
        {
            i = 0;
            strToken[i++] = str[nNextPos++];
            while ( is_scientific(strToken[i++] = str[nNextPos++]) )
                if (strToken[i-1] == 'd' || strToken[i-1] == 'D') strToken[i-1] = 'e';
            strToken[i - 1] = '\0';
            --nNextPos;
            token->Type = VALUE;
            strcpy(token->str, strToken);
            token->Value = atof(strToken);
            return VALUE;
        }
        else if ( str[nNextPos] == '(' )
        {
            token->Type = OPAREN;
            strcpy(token->str, "(");
            ++nNextPos;
            return OPAREN;
        }
        else if ( str[nNextPos] == ')' )
        {
            token->Type = CPAREN;
            strcpy(token->str, ")");
            ++nNextPos;
            return CPAREN;
        }
        else if ( str[nNextPos] == '+' )
        {
            strcpy(token->str, "+");
            ++nNextPos;
            if ( !bIsInfix )
            {
                token->Type = PLUS;
                return PLUS;
            }
            else
            {
                if ( PreviousTokenType == CPAREN || PreviousTokenType == VALUE )
                {
                    token->Type = PLUS;
                    return PLUS;
                }
                else
                {
                    token->Type = UPLUS;
                    return UPLUS;
                }
            }
        }
        else if ( str[nNextPos] == '-' )
        {
            strcpy(token->str, "-");
            ++nNextPos;
            if ( !bIsInfix )
            {
                token->Type = MINUS;
                return MINUS;
            }
            else
            {
                if ( PreviousTokenType == CPAREN || PreviousTokenType == VALUE )
                {
                    token->Type = MINUS;
                    return MINUS;
                }
                else
                {
                    token->Type = UMINUS;
                    return UMINUS;
                }
            }
        }
        else if ( str[nNextPos] == '~' )
        {
            strcpy(token->str, "~");
            ++nNextPos;
            if ( !bIsInfix )
            {
                token->Type = UMINUS;
                return UMINUS;
            }
            else
            {
                token->Type = UNKNOWN;
                return UNKNOWN;
            }
        }
        else if ( str[nNextPos] == '*' )
        {
            token->Type = MULT;
            strcpy(token->str, "*");
            ++nNextPos;
            return MULT;
        }
        else if ( str[nNextPos] == '/' )
        {
            token->Type = DIV;
            strcpy(token->str, "/");
            ++nNextPos;
            return DIV;
        }
        else if ( str[nNextPos] == '^' )
        {
            token->Type = EXP;
            strcpy(token->str, "^");
            ++nNextPos;
            return EXP;
        }
        else
        {
            token->Type = UNKNOWN;
            token->str[0] = str[nNextPos];
            token->str[1] = '\0';
            ++nNextPos;
            return UNKNOWN;
        }
    }

    return EOL;
}


double BinaryOperation(double left, double right, char op, char* strError)
{
    strcpy(strError, "");

    switch ( op )
    {
    case '-':
        return left - right;
    case '+':
        return left + right;
    case '*':
        return left * right;
    case '/':
        if ( right == 0 )
        {
            sprintf(strError, "Error: division by zero!\n");
            return 0.0;
        }
        else
            return left / right;
    case '^':
        return pow(left, right);
    default:
        if ( op == '(' )
            sprintf(strError, "Error: unbalanced brackets.\n");
        else
            sprintf(strError, "Error: unknown operator: %c\n", op);
        return 0.0;
    }
}


double EvalInfix(const char *strExpression, char * strError)
{
    Token tok;
    Token tok_temp;
    double left, right;
    double dblRet;

    strcpy(strError, "");

    tok_temp.Type = EOL;
    tok_temp.str[0] = '@';
    tok_temp.str[1] = '\0';
    push_op(tok_temp, strError);
    if ( strError[0] != '\0' )
        return 0.0;

    left = right = 0.0;
    while ( (PreviousTokenType = GetNextToken(strExpression, &tok, TRUE)) != EOL )
    {
        if ( tok.Type == UNKNOWN )
        {
            sprintf(strError, "Error: invalid token: %s\n", tok.str);
            return 0.0;
        }
        else if ( tok.Type == VALUE )
        {
            push_val(tok.Value, strError);
            if ( strError[0] != '\0' )
                return 0.0;
        }
        else if ( tok.Type == OPAREN || tok.Type == UMINUS || tok.Type == UPLUS )
        {
            push_op(tok, strError);
            if ( strError[0] != '\0' )
                return 0.0;
        }
        else if ( tok.Type == CPAREN )
        {
            while ( top_op(strError).Type != OPAREN )
            {
                if ( strError[0] != '\0' )
                    return 0.0;

                tok_temp = pop_op(strError);
                if ( strError[0] != '\0' )
                    return 0.0;

                if ( (tok_temp.Type == EOL) || (is_empty_op()) )
                {
                    sprintf(strError, "Error: unbalanced brackets.\n");
                    return 0.0;
                }

                right = pop_val(strError);
                if ( strError[0] != '\0' )
                    return 0.0;

                if ( tok_temp.Type != UMINUS )
                {
                    left = pop_val(strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    dblRet = BinaryOperation(left, right, tok_temp.str[0], strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    push_val(dblRet, strError);
                    if ( strError[0] != '\0' )
                        return 0.0;
                }
                else
                {
                    push_val( -1 * right, strError );
                    if ( strError[0] != '\0' )
                        return 0.0;
                }
            }
            pop_op(strError);
            if ( strError[0] != '\0' )
                return 0.0;
        }
        else
        {
            while ( PREC_TABLE[ top_op(strError).Type ].topOfStack >= PREC_TABLE[ tok.Type ].inputSymbol )
            {
                if ( strError[0] != '\0' )
                    return 0.0;

                if ( top_op(strError).Type != UMINUS && top_op(strError).Type != UPLUS )
                {
                    if ( strError[0] != '\0' )
                        return 0.0;

                    right = pop_val(strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    left = pop_val(strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    tok_temp = pop_op(strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    dblRet = BinaryOperation(left, right, tok_temp.str[0], strError);
                    if ( strError[0] != '\0' )
                        return 0.0;

                    push_val(dblRet, strError);
                    if ( strError[0] != '\0' )
                        return 0.0;
                }
                else
                {
                    if ( top_op(strError).Type == UMINUS )
                    {
                        if ( strError[0] != '\0' )
                            return 0.0;

                        right = pop_val(strError);
                        if ( strError[0] != '\0' )
                            return 0.0;

                        pop_op(strError);
                        if ( strError[0] != '\0' )
                            return 0.0;

                        push_val(-1 * right, strError);
                        if ( strError[0] != '\0' )
                            return 0.0;
                    }
                    else
                    {
                        pop_op(strError);
                        if ( strError[0] != '\0' )
                            return 0.0;
                    }
                }
            }

            if ( tok.Type != EOL )
            {
                push_op(tok, strError);
                if ( strError[0] != '\0' )
                    return 0.0;
            }
        }
    }

    while ( 1 )
    {
        tok_temp = pop_op(strError);
        if ( strError[0] != '\0' )
            return 0.0;

        if ( tok_temp.Type == EOL )
            break;

        if ( tok_temp.Type != UPLUS )
        {
            right = pop_val(strError);
            if ( strError[0] != '\0' )
                return 0.0;
        }

        if ( tok_temp.Type != UMINUS && tok_temp.Type != UPLUS )
        {
            left = pop_val(strError);
            if ( strError[0] != '\0' )
                return 0.0;

            dblRet = BinaryOperation(left, right, tok_temp.str[0], strError);
            if ( strError[0] != '\0' )
                return 0.0;

            push_val(dblRet, strError);
            if ( strError[0] != '\0' )
                return 0.0;
        }
        else
        {
            push_val( -1 * right, strError );
            if ( strError[0] != '\0' )
                return 0.0;
        }
    }

    dblRet = pop_val(strError);
    if ( strError[0] != '\0' )
        return 0.0;

    if ( is_empty_val() )
    {
        return dblRet;
    }
    else
    {
        sprintf(strError, "Error: malformed expression.\n");
        return 0.0;
    }
}

double eval_infix( int *ierr, const char *strExpression, int len )
{
  double result = 0.0;
  char strHelper[257];
  char strError[257];
  int i;


  if (len>256) {
    printf("[eval_infix.c] expression longer than 256 characters\n");
    ierr[0] = 1;
    return result;
  }

 
  for(i=0;i<len;i++) strHelper[i]=' ';
  strHelper[len] = '\0'; 

  for(i=0;i<len;i++) strHelper[i] = strExpression[i];

  for(i=0;i<len;i++) strError[i] = ' ';
  strError[len] = '\0';

  result =  EvalInfix(strHelper, strError);

  if ( strError[0] != '\0' ) {
    printf("[eval_infix.c] A parsing error occurred\n");
    
    printf("helper string:\n%s\n", strHelper);
    printf("error code:   \n%s\n", strError);
    ierr[0] = 1;
  }
  else ierr[0] = 0;

  return result;
}