In this assignment, you are required to write your own generic stack implementat
ID: 3809361 • Letter: I
Question
In this assignment, you are required to write your own generic stack implementation in Java, and use this implementation to convert and evaluate arithmetic expressions. Your code must handle the general expressions, and not just those that are fully paranthesized. Details are provided below. 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 (wherever needed). 2. Infix to Postfix conversion Write a class called InfixToPostfixConverter. This class, as its name suggests, 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. c. You should assume no whitespace in the infix expression provided by the user. For example, your code should work for inputs like “2+3.5×2”. The postfix that you will print, however, should have tokens separated by whitespace. For example, “3.5×21” should have the postfix “3.5 21 ×”, and not “3.521×”. Important Notes • You may not use any Java data structures directly (other than arrays). Using Java’s native data structures in this homework will result in a zero score. Note that you will not need to use linked list for this stack implementation. • There are points in this homework for properly using Java keywords. For instance, don’t fill up your code with new instances of the same variable. If you are repeatedly using a particular value, use the suitable Java keywords. (Hint: Think in terms of examples like “public static final PI” that we have discussed.) • It may be useful to look into the official Java documentation1 of StringBuilder and Character.
Explanation / Answer
Hi, Please find my implemetnation.
Please let me know in case of any issue.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class InfixToPostfixAndEval {
public static boolean isParenthesisBalanced(String s) {
Stack<Character> stack = new Stack<>();
boolean result = true;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case ')':
if ((!stack.isEmpty()) && (stack.pop() != '(')) {
return false;
}
break;
case '}':
if ((Character) stack.pop() != '{') {
return false;
}
break;
case ']':
if ((Character) stack.pop() != '[') {
return false;
}
break;
default:
if(c=='(' || c =='[' || c=='{')
stack.push(c);
}
}
return result;
}
public static String infixToPostfix(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) || Character.isDigit(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;
}
private static int prec(char x) {
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/' || x == '%')
return 2;
return 0;
}
public static int evalPostfix(String str){
Stack<Integer> stack = new Stack<Integer>();
int i=0;
while (i < str.length()) { // iterating over all characters of postfix expression
char c = str.charAt(i);
if (Character.isDigit(c)) { // if current character is digit then push in stack
stack.push(c - '0');
i++;
continue;
}
// if current character is operator, then pop two elements from stack
int b = stack.pop();
int a = stack.pop();
if (c == '+') stack.push(a + b);
else if (c == '-') stack.push(a - b);
else if (c == '*') stack.push(a * b);
else if (c == '/') stack.push(a / b);
else if (c == '%') stack.push(a % b);
i++;
}
return stack.pop();
}
public static void main(String[] args)throws IOException
{
String input;
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
while(true)
{
System.out.println("Enter the Infix expresion(of enter Q/q to stop)");
input= br.readLine();;
if(input.equalsIgnoreCase("q"))
break;
if(isParenthesisBalanced(input)){
char[] infix = input.trim().toCharArray();
String postfix = infixToPostfix(infix);
System.out.println("Postfix Expression:- "+postfix);
System.out.println("Result of postfix: "+evalPostfix(postfix));
}else{
System.out.println("Parenthesis are not balanced in infix expression");
}
}
br.close();
isr.close();
}
}
/*
Sample run:
Enter the Infix expresion(of enter Q/q to stop)
(4+5)-5
Postfix Expression:- 45+5-
Result of postfix: 4
Enter the Infix expresion(of enter Q/q to stop)
(4+5}-5
Parenthesis are not balanced in infix expression
Enter the Infix expresion(of enter Q/q to stop)
q
*/