Converting Infix Expression to Postfix Expression Use stack. This is done by fir
ID: 3814094 • Letter: C
Question
Converting Infix Expression to Postfix Expression
Use stack. This is done by first converting an expression from infix notation, which is our standard notation, to postfix notation. You are asked to write a program that convert infix to postfix expression.
The user will be asked to enter an expression in infix notation. To make the conversion simple, the user should enter the expression as a String. Instead of using numbers, we will use capital letters. For example, an input could be A + B * C. Each token of our string should be separated by a single space. If each component of the expression is separated by a single space, we can parse the string and have each token be stored in an array. To do this, we can invoke the split() method on the string itself. The method takes a single argument, which serves as our delimiter, which is the character that separates each token. In this case, our delimiter is a single space (i.e., " "). This method returns an array, so you have the result of the method be stored in an array of Strings. You can then look at each element of the array using a foreach loop and follow the algorithm discussed in class.
For the stack implementation, you may use either the MyStack class that I provided or the Stack class provided by Java. As each item is popped from the stack, make sure the popped item is 1 printed. The output itself should be on a single line, and each part of the expression should be separated by a single space
Explanation / Answer
Algorithm mentioned in your class was not provided, So I have used my own algorithm and implemented this. Hope it works out for you. I am considering only inputs with space after each element here as mentioned in the question. Here is the code below: -
import java.util.Scanner;
import java.util.Stack;
// Class to convert from infix to Postfix
public class InfixToPostFix {
// method to check if character is operator . Returns true if operator else false
private static boolean isOper(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c == '(' || c == ')';
}
//method to check which operator has less precidence
private static boolean isLessPrec(char a, char b)
{
switch (a)
{
case '+':
case '-':
return !(b == '+' || b == '-');
case '*':
case '/':
return b == '^' || b == '(';
case '^':
return b == '(';
case '(':
return true;
default:
return false;
}
}
//Actual method for conversion
public static String convertToPostfix(String infix)
{
Stack<Character> stack = new Stack<Character>();// using a character stack for the operations
StringBuffer postfix = new StringBuffer(infix.length());
String strArray[] = infix.split(" ");// splitting string with spaces to string array
char c;
for (int i = 0; i < strArray.length; i++)
{
c = strArray[i].charAt(0);// getting each element of array converted to char
if (!isOper(c)) // if not operator than add to String buffer.
{
postfix.append(c);
postfix.append(' '); // adding a space after each element added to string buffer
}
else // of operator do stack operations
{
if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
{
postfix.append(stack.pop());
postfix.append(' ');
}
if (!stack.isEmpty())
{
stack.pop();
}
}
else
{
if (!stack.isEmpty() && !isLessPrec(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLessPrec(c, stack.peek()))
{
Character pop = stack.pop();
if (c != '(')
{
postfix.append(pop);
postfix.append(' ');
} else {
c = pop;
}
}
stack.push(c);
}
}
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
postfix.append(' ');
}
return postfix.toString(); //postfix returned as string.
}
public static void main(String[] args)
{
System.out.println("Input the infix expression(separated with spaces):");
Scanner input = new Scanner(System.in); // taking input from the user using Scanner
String line;
while (!"q".equals(line = input.nextLine())) {
System.out.println("Converted expression to Postfix: " +convertToPostfix(line));
}
}
}
Output: -
Input the infix expression(separated with spaces):
A * B - ( C + D ) + E
Converted expression to Postfix: A B * C D + - E +