Java program that convert infix notation to prefix notation?

Answer 1

The following class should convert prefix to infix expression. I hope the logic is pretty simple and easy to understand. For any queries contact me at keepintouchsk@gmail.com

// Author: Skay

// Date: Nov 7, 2010

import java.util.Stack;

import java.util.Enumeration;

public class PrefixToInfixConverter

{

public static Stack<String> infixStk = new Stack<String>();

public PrefixToInfixConverter() { }

public static boolean isOper(String tstr)

{

if( tstr.equals("+") tstr.equals("-") tstr.equals("*") tstr.equals("/") )

return true;

else

return false;

}

public static String convert(String prefixStr)

{

String infixStr=new String();

String tempString = new StringBuffer(prefixStr).reverse().toString();

for(int i=tempString.length()-1;i>=0;i--)

{

while(tempString.charAt(i)==' ')

i--;

infixStk.push(String.valueOf(tempString.charAt(i)));

}

String[] val = new String[50];

int i,j;

while(infixStk.size()>1)

{

i=0;

while(!isOper(val[i++]=infixStk.pop()));

val[i-3] = new String("(" + val[i-2] + val[i-1] + val[i-3] + ")" );

for(j=i-3;j>=0;j--)

infixStk.push(val[j]);

}

return infixStk.pop();

}

}

Input: /-ab*c+de Output: ((a-b)/(c*(d+e)))

Answer 2

/**

* Provides a collection of methods to convert postfix expressions to infix.

* Since expressions can contain both numbers and mathematical operators, all

* expressions use String objects to represent each part of the expression. The

* methods in this class are made to accept postfix expressions in any of the

* following formats:

* 1) String - Example: "3 4 +"

* 2) String[] - Example: {"3", "4", "+"}

* 3) Iterator<String> - Like String[], but for expressions in Collection objects

* 4) Iterable<String> - See above

*

* All methods translate their data into an Iterator<String>, and defer to that

* method to perform the actual parsing/translation.

*

* All methods will then also have the same return type: a String containing the

* unambiguous infix conversion of the postfix expression.

*

* Since all expressions have the possibility of being incorrectly formatted,

* the ExpressionFormatException is thrown if this is detected during processing.

*

* To accomodate algebraic expressions, values are not restricted by the characters

* they can represent. Numbers, letters, and all other non-operator symbols are

* allowed. "a b +" is perfectly valid input.

*

* These methods are designed to convert between one notation and the other; they

* will not find a numerical solution to any expressions.

*/

public final class PostfixToInfix {

/**

* Actual conversion method. Takes the expression stored in postfix and returns

* an infix representation of it.

*/

public static final String postfixToInfix(final Iterator<String> postfix)

throws ExpressionFormatException {

// Stack to hold values

final Stack<String> tokenStack = new Stack<String>();

// Start processing tokens

while (postfix.hasNext()) {

final String currentToken = postfix.next();

// Evaluate the current token and push it onto the stack

tokenStack.push(evaluateToken(currentToken, tokenStack));

}

// There should be exactly one element on the stack. Anything else

// signifies an input error.

if (tokenStack.size() != 1) {

throw new ExpressionFormatException();

}

// Last element of the stack is our result

return tokenStack.pop();

}

/**

* If token is a value, return the token.

* If token is an operator, perform the operation and return the result.

*/

private static final String evaluateToken(final String token, final Stack<String> tokenStack)

throws ExpressionFormatException {

if (isOperator(token)) {

// We know each operator works on two numbers...

// Check for correct number of values on stack

if (tokenStack.size() < 2) {

throw new ExpressionFormatException();

}

// Grab values to evaluate from stack

final String value2 = tokenStack.pop();

final String value1 = tokenStack.pop();

// Return evaluated expression

return "(" + value1 + " " + token + " " + value2 + ")";

} else { // currentToken = number

// If token is a number, it goes right onto the stack

return token;

}

}

// Overloaded variations of postfixToInfix method. Each just converts an

// expression from one format to Iterator<String> and calls that method.

public static final String postfixToInfix(final Iterable<String> postfix)

throws ExpressionFormatException {

return postfixToInfix(postfix.iterator());

}

public static final String postfixToInfix(final String[] postfix)

throws ExpressionFormatException {

return postfixToInfix(new ArrayIterator(postfix));

}

public static final String postfixToInfix(final String postfix)

throws ExpressionFormatException {

return postfixToInfix(new StringIterator(postfix));

}

/**

* Returns true iff token is a mathematical operator.

*

* Note: This method is a little over-the-top. It checks for every possible

* variation on mathematical characters. In the case of multiplication,

* there are a lot of variations on asterisks, 'x's, and dot notations.

* Typically the only real reason for this is for completeness.

*/

private static final boolean isOperator(final String token) {

// We can stop negative numbers from being identified as

// operators with this check.

if (token.length() == 1) {

// Ugliness

switch (token.charAt(0)) {

// Addition

case '+':

// Division

case '/':

case '\u0338':case '\u2044':case '\u2215':case '\u00F7':

// Subtraction

case '-':case '\u2010':case '\u2011':case '\u2012':

case '\u2013':case '\u2014':case '\u2015':case '\u2212':

// Multiplication

case 'x':case 'X':case '*':

case '\u00B7':case '\u0387':case '\u05BC':case '\u2022':

case '\u2027':case '\u2219':case '\u22C5':case '\u30FB':

case '\uFF65':case '\u00D7':case '\u2573':case '\u2715':

case '\u066D':case '\u203B':case '\u2217':case '\u2722':

case '\u2723':case '\u2724':case '\u2725':case '\u2731':

case '\u2732':case '\u2733':case '\u273A':case '\u273B':

case '\u273C':case '\u273D':case '\u2743':case '\u2749':

case '\u274A':case '\u274B':case '\uFE61':case '\uFF0A':

return true;

}// switch

}// if

return false;

}

// Conversion classes - used by postfixToInfix overloads to convert various

// datatypes to Iterator<String> types.

private static final class ArrayIterator implements Iterator<String> {

private final String[] strs;

private int index;

private ArrayIterator(final String[] strs) {

this.strs = strs;

index = 0;

}

public final boolean hasNext() {

return (index < strs.length);

}

public final String next() {

return strs[index++];

}

public final void remove() {

}

}

private static final class StringIterator implements Iterator<String> {

private final StringTokenizer stringtokenizer;

private StringIterator(final String str) {

stringtokenizer = new StringTokenizer(str);

}

public final boolean hasNext() {

return stringtokenizer.hasMoreTokens();

}

public final String next() {

return stringtokenizer.nextToken();

}

public final void remove() {

}

}

// Special Exception

private static final class ExpressionFormatException

extends IllegalArgumentException {

private ExpressionFormatException() {

}

}

}// PostfixToInfix

Answer 3

System.out.print("Enter the Element you want to sort[THEN PRESS ENTER]:");

num=new Scanner(System.in).nextInt();

}

int num,i;

Answer 4

Creamed on corn.