Question

in Java

In this exercise, you'll write a Java version of the infix-to-postfix conversion algorithm. These same mechanisms can be used as a part of writing a simple compiler.

Write class InfixToPostfixConverter co convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers (to make things easier) such as

(6 + 2) • 5 - 8 / 4

to a postfix expression. The postfix version (no parentheses are needed) of this infix expression is

6 2 + 5 * 8 4 / -

The program should read the expression into StringBuilder or String infix and use the Stack and Stack Interface class (as found in Lesson 8 Programs Classwork) to help create the postfix expression in StringBuuider (or String) postfix. The algorithm for creating a postfix expression is shown below

Push a left parenthesis ' (' onto the stack.

Append a right parenthesis ') ' to the end of infix.

While the stack is not empty, read infix from left to right and do the following:

     If the current character in infix is a digit, append it to postfix.

     If the current character in infix is a left parenthesis, push it onto the stack.

     If the current character in infix is an operator:

            Pop operators (if there are any) at the top of the stack while they have equal or higher

precedence than the current operator, and append the popped operators to postfix.

     Push the current character in infix onto the stack.

     If the current character in infix is a right parenthesis:

            Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack.

            Pop (and discard) the left parenthesis from the stack.

The following arithmetic operations are allowed in an expression:

^ exponentiation

* multiplication

/ division

% remainder

+ addition

- subtraction

Exponents have the highest precedence, multiplication, division and remainder all share the next highest precedence, and addition and subtraction have the lowest precedence.

Some methods you may want to provide are as follows:

Method convertToPostfix, which accepts converts the infix expression to postfix notation by implementing the algorithm described above.

Method is0perator, which determines whether the input parameter c is an operator.

Method precedence, which determines whether the precedence of operator1 (from the infix expression) is less than, equal to or greater than that of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned. Precedence is as defined above.

You will need to use the Stack method peek to perform some of the checks as described above

Answer 1

import java.util.Stack;

class Test

{

// A utility function to return precedence of a given operator

// Higher returned value means higher precedence

static int Prec(char ch)

{

switch (ch)

{

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

}

return -1;

}

}

// The main method that converts given infix expression

// to postfix expression.  

static String infixToPostfix(String exp)

{

// initializing empty String for result

String result = new String("");

  

// initializing empty stack

Stack<Character> stack = new Stack<>();

  

for (int i = 0; i<exp.length(); ++i)

{

char c = exp.charAt(i);

  

// If the scanned character is an operand, add it to output.

if (Character.isLetterOrDigit(c))

result += c;

// If the scanned character is an '(', push it to the stack.

else if (c == '(')

stack.push(c);

  

// If the scanned character is an ')', pop and output from the stack  

// until an '(' is encountered.

else if (c == ')')

{

while (!stack.isEmpty() && stack.peek() != '(')

result += stack.pop();

  

if (!stack.isEmpty() && stack.peek() != '(')

return "Invalid Expression"; // invalid expression

else

stack.pop();

}

else // an operator is encountered

{

while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){

if(stack.peek() == '(')

return "Invalid Expression";

result += stack.pop();

}

stack.push(c);

}

}

// pop all the operators from the stack

while (!stack.isEmpty()){

if(stack.peek() == '(')

return "Invalid Expression";

result += stack.pop();

}

return result;

}

  

// Driver method  

public static void main(String[] args)  

{

String exp = '(6 + 2) • 5 - 8 / 4';

System.out.println(infixToPostfix(exp));

}

}