Postfix Conversion

Program Description

Class Diagram: see image.

You need to complete the precedence and convertToPostfix methods in the PostFixConversion class.

Instruction:

The PostfixConversion class is a class that has a utility that converts an infix expression to its postfix expression. It does not have any class level (instance) variables. It must have the following two static methods:

public static boolean precedence(char first, char second)

The precedence method determines the precedence between two operators. (here, they are either '+', '-', '*', or '/') If the first operator is of higher or equal precedence than the second operator, it returns the value true; otherwise, it returns the value false. (for instance, if the new operator is '+' or '-', then all operators (+,-,*,/) have precedence greater than or equals to the operator. If the new operator is '*' or '/', then only the operators '*' and '/' have precedence greater than or equals to the operator.) This method will be called from the convertToPostfix method described below.

public static String convertToPostfix(String infixExp)

The convertToPostfix method converts the infix expression (the parameter string for this method) into a postfix expression.

1. If all parentheses are matching in the input infix expression string, then computes its postfix expression, and the method should return the string as:

"The Postfix Expression is: ABC++DHTY++R-*-"

Here, ABC++DHTY++R-*- is an example of postfix expression and the correct one for each input should be displayed instead of it.

2. If there is an open parenthesis that does not have its corresponding close parenthesis, then for the first such character, return a string with the message as:

"There is no matching close parenthesis."

For instance, if the input infix expression string is:

(A+(B+C)

then for the first open parenthesis, there is no corresponding close parenthesis. In this case, the above message should be returned instead of any post fix expression.

3. If there is a close parenthesis that does not have its corresponding open parenthesis, then for the first such character, return a string with the message as:

"There is no matching open parenthesis."

For instance, if the input infix expression string is:

A)+(B+C)

then for the first close parenthesis, there is no corresponding open parenthesis. In this case, the above message should be returned instead of any post fix expression.

a. Check/scan each character of a given infix expression (a string) from left to right. (One pass is sufficient.)

b. If the next scanned symbol (character) is an operand (here only alphabet letters - both upper cases and lower cases are used.), append it to the postfix expression.

c. If the next scanned symbol (character) is an open parenthesis '(', then push it onto the stack.

d. If the next scanned symbol (character) is a close parenthesis ')', then pop and append all the symbols from the stack until the most recent matching open parenthesis. i.e., pop and append all the symbols above the open parenthesis that is located in the highest position in the stack. Then pop and discard that open parenthesis at the highest position in the stack.

e. If the next scanned symbol (character) is an operator (here, they are either '+', '-', '*', or '/'),

i). Pop and append to the postfix expression every operator from the stack that is above the most recently scanned open parenthesis, and that has precedence greater than or equals to the new operator (for instance, if the new operator is '+' or '-', then all operators (+,-,*,/) have precedence greater than or equals to the operator. If the new operator is '*' or '/', then only the operators '*' and '/' have precedence greater than or equals to the operator.)

ii). Push the new operator onto the stack.

f. After the infix string is completely processed, pop and append to the postfix string everything from the stack.

In this program, you are to consider the following (binary) arithmetic operators only: +, -, *, and /.

Requirements:

You need to implement this method using an object of the Stack class in java.util package. One way to utilize it is to treat it as a stack of Character objects. The Character class is a wrapper class for the primitive data type "char". If you use the compiler version 5 or above, you can use Auto-boxing for automatic conversion between a primitive data character and an object of the Character class.

To manually convert between them, you can make use of some methods in the Character class such as:

valueOf() method (an example below to convert a character '(' to an object)

Character obj = Character.valueOf('(');

charValue() method (an example below to convert a Character object to a primitive data type character)

char char1 = obj.charValue();