Amazon Affiliate

Tuesday 27 March 2012

CONVERT PREFIX TO POSTFIX EXPRESSION IN C++

#include <fstream.h>
#include <string.h>

//    Prototype Declarations
void preToPostFix  (char *preFixIn, char *exprOut);
int  findExprLen   (char *exprIn);

int main (void)
{
//    Local Definitions
    char  preFixExpr[256]  = "-+*ABC/EF";
    char  postFixExpr[256] = "";
   
//    Statements
    cout << "Begin prefix to postfix conversion\n\n";
   
    preToPostFix (preFixExpr, postFixExpr);
    cout << "Prefix expr:  " << preFixExpr  << endl;
    cout << "Postfix expr: " << postFixExpr << endl;
   
    cout << "\nEnd prefix to postfix conversion\n";
    return 0;
}    // main
   
/*    ==================== preToPostFix ====================
    Convert prefix expression to postfix format.
       Pre   preFixIn is string containing prefix expression
                expression can contain no errors/spaces
             postFix is string variable to receive postfix
       Post  expression has been converted
*/
void preToPostFix (char *preFixIn,
                   char *postFix)
{
//    Local Definitions
    char  operatr [2];
    char  postFix1[256];
    char  postFix2[256];
    char  temp    [256];
    int   lenPreFix;
   
//    Statements
    if (strlen(preFixIn) == 1)
       {
        *postFix       = *preFixIn;
        *(postFix + 1) = '\0';
        return;
       } // if only operand
      
    *operatr       = *preFixIn;
    *(operatr + 1) = '\0';
   
    // Find first expression
    lenPreFix = findExprLen (preFixIn + 1);
    strncpy (temp, preFixIn + 1, lenPreFix);
    *(temp + lenPreFix) = '\0';
    preToPostFix (temp, postFix1);
   
    // Find second expression
    strcpy (temp, preFixIn + 1 + lenPreFix);
    preToPostFix (temp, postFix2);
   
    // Concatenate to postFix
    strcpy (postFix, postFix1);
    strcat (postFix, postFix2);
    strcat (postFix, operatr);
   
    return;
}    // preToPostFix

/*    ==================== findExprLen ====================
    Determine size of first prefix substring in an expression.
       Pre   exprIn contains prefix expression
       Post  size of expression is returned
*/
int findExprLen (char *exprIn)
{
//    Local Definitions
    int  lenExpr1;
    int  lenExpr2;

//    Statements
    switch (*exprIn)
       {
        case '*':
        case '/':
        case '+':
        case '-':
             // Find length of first prefix expression
             lenExpr1  =  findExprLen (exprIn + 1);

             // Find length of second prefix expression
             lenExpr2  =  findExprLen (exprIn + 1 + lenExpr1);
             break;
        default:
             // base case--first char is operand
             lenExpr1 = lenExpr2 = 0;
             break;
       } // switch
    return lenExpr1 + lenExpr2 + 1;
}

No comments:

Post a Comment