import java.util.Stack;
import java.util.Scanner;
public class ExpressionConverter {
// Function to return precedence of operators
static int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1; // For non-operators
}
// Function to convert infix to postfix
static String infixToPostfix(String expression) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
// If the character is an operand, add it to the output
if (Character.isLetterOrDigit(c)) {
result.append(c);
}
// If the character is '(', push it to stack
else if (c == '(') {
stack.push(c);
}
// If the character is ')', pop from stack to output until '(' is encountered
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop(); // Discard the '('
}
}
// If an operator is encountered
else {
// Pop operators with higher or equal precedence from the stack
while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
result.append(stack.pop());
}
stack.push(c);
}
}
// Pop all the remaining operators from the stack
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}
// Function to convert infix to prefix
static String infixToPrefix(String expression) {
// The algorithm for infix to prefix is:
// 1. Reverse the infix expression.
// 2. Swap '(' and ')' in the reversed expression.
// 3. Convert the modified expression to postfix.
// 4. Reverse the resulting postfix expression to get the prefix expression.
StringBuilder reversedInfix = new StringBuilder(expression).reverse();
for (int i = 0; i < reversedInfix.length(); i++) {
char c = reversedInfix.charAt(i);
if (c == '(') {
reversedInfix.setCharAt(i, ')');
} else if (c == ')') {
reversedInfix.setCharAt(i, '(');
}
}
// Convert the modified string to postfix
String postfixForReversed = infixToPostfix(reversedInfix.toString());
// Reverse the result to get prefix
return new StringBuilder(postfixForReversed).reverse().toString();
}
// Main method to test the conversion
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter an infix expression (use single letters/digits and operators, no spaces, e.g., a+b*c): ");
String infixExpression = scanner.nextLine();
String postfix = infixToPostfix(infixExpression);
String prefix = infixToPrefix(infixExpression);
System.out.println("Infix Expression: " + infixExpression);
System.out.println("Postfix Expression: " + postfix);
System.out.println("Prefix Expression: " + prefix);
}
}
