Write a Java algorithm to convert and evaluate an Infix expression and converts
ID: 3684819 • Letter: W
Question
Write a Java algorithm to convert and evaluate an Infix expression and converts it to postfix, and then evaluates it.
1. Generic Stack Implementation
a. Your stack class must contain a private static nested class called Node.
b. Your stack must have all instance variables as private.
c. It must have the stack operation methods isEmpty, peek, pop, push and size. Remember to carefully deal with exceptions in these methods.
2. Infix to Postfix conversion Write a class called InfixToPostfixConverter. This class, will be responsible for converting infix expressions to postfix expressions using your stack implementation.
a. Your class must contain a public String convert(char[] infix) method that takes as input an infix expression, and outputs the equivalent postfix expression.
3. Evaluating a Postfix expression Write a class called PostfixEvaluator to evaluate postfix expressions.
a. It must contain a public int evaluate(char[] postfix) method.
b. It must contain a public static void main(String[] args) method to run your code. This main method should ask the user to input one infix expression per line until the user types “q” or “Q”. After every input, it should print out the equivalent postfix expression, and the final value of the expression, and then ask for the next input.
Explanation / Answer
############ Stack.java ########################
public class Stack<T> {
private int size = 0;
private Node<T> root = null;
/*
* It has to return the size of the NodeList
*
* @return size
*/
public int size() {
return size;
}
// add an element to the stack
public void push(T item) {
Node<T> oldfirst = root;
root = new Node<T>(item, oldfirst);
size++;
}
// delete and return the most recently added element
public T pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
T item = root.getData(); // save item to return
root = root.getNext(); // delete first node
size--;
return item; // return the saved item
}
// is the stack empty?
public boolean isEmpty() { return root == null; }
// delete and return the most recently added element
public T peek() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
T item = root.getData(); // save item to return
return item; // return the saved item
}
//Node Class
static class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
public Node(T data, Node<T> next){
this.data = data;
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public String toString() {
return "Data: "+ data.toString();
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
}
################## InfixToPostfixConverter.java ###################
public class InfixToPostfixConverter {
public String convert(char[] infix)
// converts an infix expression to postfix
{
Stack<Character> operators = new Stack<Character>();
char symbol;
String postfix = "";
for (int i = 0; i < infix.length; ++i)
// while there is input to be read
{
symbol = infix[i];
// if it's an operand, add it to the string
if (Character.isLetter(symbol))
postfix = postfix + symbol;
else if (symbol == '(')
// push (
{
operators.push(symbol);
} else if (symbol == ')')
// push everything back to (
{
while (operators.peek() != '(') {
postfix = postfix + operators.pop();
}
operators.pop(); // remove '('
} else
// print operators occurring before it that have greater precedence
{
while (!operators.isEmpty() && !(operators.peek() == '(')
&& prec(symbol) <= prec(operators.peek()))
postfix = postfix + operators.pop();
operators.push(symbol);
}
}
while (!operators.isEmpty())
postfix = postfix + operators.pop();
return postfix;
}
public int prec(char x) {
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/' || x == '%')
return 2;
return 0;
}
}
#################### PostfixEvaluator.java ###############
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class PostfixEvaluator {
public int evaluate(char[] postfix) {
int n, r = 0;
n = postfix.length;
Stack<Integer> a = new Stack<Integer>();
for (int i = 0; i < n; i++) {
char ch = postfix[i];
if (ch >= '0' && ch <= '9')
a.push(ch - '0');
else if (ch == ' ')
continue;
else {
int x = a.pop();
int y = a.pop();
switch (ch) {
case '+':
r = x + y;
break;
case '-':
r = y - x;
break;
case '*':
r = x * y;
break;
case '/':
r = y / x;
break;
default:
r = 0;
}
a.push(r);
}
}
r = a.pop();
return (r);
}
// main method
public static void main(String[] args)throws IOException
{
// declaring object
PostfixEvaluator postfixEval = new PostfixEvaluator();
InfixToPostfixConverter infixToPostfix = new InfixToPostfixConverter();
String input;
while(true)
{
System.out.println("Enter the Infix expresion(of enter Q/q to stop)");
input=getString();
if(input.equalsIgnoreCase("q"))
break;
char[] infix = input.trim().toCharArray();
String postfix = infixToPostfix.convert(infix);
System.out.println("Postfix Expression:- "+postfix);
System.out.println("Evaluated value of postfix: "+postfixEval.evaluate(postfix.toCharArray()));
}
}
public static String getString()throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}