Conversion of Prefix Expressions to Postfix Format

Due Date: February 23

In this program, you are to write a program that uses recursion to convert a prefix expression to the postfix format. First let’s look at different ways to represent an arithmetic expression. It can be represented in three different formats: infix, postfix, and prefix. In infix notation, the operator (+, -, *, /) comes between the two operands. This is the notation that we learned in grammar school. In postfix notation, the operator comes after its two operands, and in prefix notation it comes before the two operands. These formats are show in the expression below:

Prefix: + a b

Infix: a + b

Postfix: a b +

One of the disadvantages of the infix notation is that we need to use parenthesis to control the evaluation of the operators. We thus have an evaluation method that includes parenthesis and two operator priority classes (* and / are evaluated first then + and -). In the postfix and prefix notations, we do not need parenthesis: each provides only one evaluation rule.

Although high-level languages use the infix notation, such expressions cannot be directly evaluated. Rather, they must be analyzed to determine the order in which the expressions are to be evaluated. A common evaluation technique is to convert the expression to postfix or prefix notation before generating the code to evaluate them. More about these three notations will be discussed in class.

For this program, we will convert a prefix expression to a postfix expression. Given the following prefix expression: * a b

we convert it to postfix by moving the operator (*) after the operands (a and b). Thus the postfix format would be: a b *

To keep the algorithm as simple as possible, we assume that each operand is only one character and that there are only four binary operators: +, -, *, and /.

As stated, to convert a prefix expression to postfix, we must find its operator and move it after the two operands. Since it is a prefix expression, the operator will be the first character in the prefix string. Following the operator are its two operands. As the expression grows in complexity, however, we can have multiple operators and operands in an expression. Consider the following prefix expression:

- + * a b c / e f

This expression consists of several binary expressions combined into one complex expression. To parse it, we begin at the left and work right until we isolate one binary expression, in this case * a b. Once we have a simple prefix expression, we can convert it to postfix and put it in the output.

For your recursive algorithm, use as your base case an expression with a single character. If an expression contains a single character then it must be an operand. For this base case, the output would be the single character.

In general, the algorithm must find the operator and the left and right operands in the binary expression. Once these are found, they can be concatenated into one postfix expression.

To find the left and right operands, a second algorithm is needed that determines the length of a prefix expression. The length of an expression is the length of the first subexpression plus the length of the second expression plus 1 for the operator. The following pseucocode may be used to help design your program.

Function preToPostFix (string preFixIn, string postFixOut)

//IN //OUT

This function converts a prefix string to a postfix string

Precondition: preFixIn is a valid string containing a prefix expression.

Postcondition: postFixOut contains the converted string in postfix notation.

1. Base Case: one character string is an operand

a. if (length of preFixIn is 1)

i. postFixOut = preFixIn

ii. return

2. If not an operand, must be an operator so:

a. Operator = first character of preFixIn

3. Must find the first expression

a. LengthOfExpr = findExprLen (preFixIn less first character)

b. Temp = substring (preFixIn[2, lengthOfExpr])

c. preToPostFix (temp, postFix1)

4. Find the second postfix expression

a. Temp = prefixIn[lengthOfExpr + 1, end of string]

b. preToPostFix (temp, postFix2)

5. Concatenate postfix expressions and operator and return

The algorithm is rather straightforward. The most difficult part is finding the prefix expression. We find it by determining its length and then storing it in a temporary string. The notation in 3b indicates that the substring starting at the first location and through the second location is to be assigned to temp. Once we have identified a prefix expression, we recursively call the function again (3c) to convert it to postfix.

To determine the length of the prefix expression, the function findExprLen() is used. Once again, the base case is finding an operand. From the definition of the problem, we know that each operand is one character long. The minimum length of a prefix expression is therefore three: one for the operator and one for each operand. As the expression is recursively decomposed, we continue to add the size of its combined expressions until we have the total length. The pseudocode below will help with this:

Function findExprLen (sting exprIn)

Recursively finds and returns the length of the first prefix substring in an expression.

Precondition: exprIn contains a valid substring that is a prefix expression

Postcondition: length of the substring is returned

1. if (first character is not an operator)

a. return 1

2. Find the length of the first prefix expression

a. lenExpr1 = findExprLen ( exprIn less one character)

3. Find the length of the second prefix expression

a. lenExpr2 = findExprLen (exprIn less (1+lenExpr1) characters)

b. return 1 + lenExpr1 + lenExpr2

Your main program should read strings (one per line) from the file prefix.dat found in $PUB, print the string in prefix, then convert it to postfix and print the resulting posfix form. Read and print until the end of file is reached on prefix.dat.