// Chapter 5, pp 233 - 234
#include <iostream.h>
#include <string.h>
#include <ctype.h>

const int MAX_STRING = 50;
typedef char expressionType[MAX_STRING+1];
void Convert(const char[], char[], int&);

void ConvertPreToPost(const char Pre[], char Post[])
// ---------------------------------------------------------
// Converts a prefix expression to postfix form.
// Precondition: Pre is an algebraic expression in
// syntactically correct prefix form. An operand is a single
// uppercase letter; an operator is one of +, -, *, and /.
// Postcondition: Post is the equivalent postfix expression;
// Pre is unchanged.
// Calls: The recursive function Convert.
// ---------------------------------------------------------
{
   // initialize
   int PreIndex = 0;
   strcpy(Post, ""); // empty string

   // do the conversion
   Convert(Pre, Post, PreIndex);
}  // end ConvertPreToPost

void Convert(const char Pre[], char Post[], int& PreIndex)
// ---------------------------------------------------------
// Recursively converts a prefix expression to postfix form.
// Precondition: The prefix expression in Pre begins at
// the index PreIndex.
// Postcondition: The prefix expression is converted to
// postfix form and concatenated to the end of Post.
// PreIndex is 1 larger than the index of the last
// character in the prefix expression.
// ---------------------------------------------------------
{
   // check the first character of the given string
   char Ch = Pre[PreIndex];          // get first character
   ++PreIndex;                       // advance index

   if (isupper(Ch))                  // check character
      // base case - single identifier
      strncat(Post, &Ch, 1);   // concatenate to end of Post
   else
   {  // do the conversion recursively
      Convert(Pre, Post, PreIndex);  // first prefix expr
      Convert(Pre, Post, PreIndex);  // second prefix expr
      strncat(Post, &Ch, 1);         // operator
   }  // end if
}  // end Convert

// ******SAMPLE MAIN PROGRAM******
main()
{  expressionType Expression, Post;

   cout << "Enter expression of no more than ";
   cout << MAX_STRING << " characters:\n";

   cin >> Expression;

   cout << "\nPrefix expression = " << Expression << "\n";

   ConvertPreToPost(Expression, Post);

   cout << "\nPostfix expression= " << Post << "\n";
   return 0;
}  // end Program