Can anyone please help with stage 1, 2, and 3? Thanks STAGE 1 | java.util.Stack
ID: 3854202 • Letter: C
Question
Can anyone please help with stage 1, 2, and 3? Thanks
STAGE 1 | java.util.Stack class public class Stack
The Stack class represents a last-in-first-out (LIFO) stack of objects. It has five operations that allow a stack be manipulated. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. When a stack is first created, it contains no items.
Constructor
Stack() : Create an empty stack Methods
Modifier and Type Method and Description
boolean empty ()
Tests if this stack is empty.
E peek ()
Looks at the object at the top of this stack without removing it from the stack.
E pop ()
Removes the object at the top of this stack and returns that object as the value of this
function.
E push ( E item)
Pushes an item onto the top of this stack.
int search ( Object o)
Returns the 1-based position where an object is on this stack.
STAGE 2 | PostFix class
Create a class called PostFix which can be used to convert an infix expression to postfix
notation.
import java.util.*;
public class PostFix {
private Stack opStack; private String postExp;
PostFix(){
opStack = new Stack(); postExp = new String();
}
public String convertToPostfix(String s) {
// Algorithm is same as InfixCalculator. Except,
// if operand append to postExp
// if op ( *,/,%,+,-) at to of stack has higher or equal precedency, then pop and // append to postExp
}
Infix expression can contain: Blanks
Operands : double values Operators : ( ) + - * / %
Operator precedency High 3: * / %
2: + - Low 1: ( )
STAGE 3 | Lab17.java
Write a driver program called “Lab17.java” and convert the following expressions using
PostFix class:
(2 + 3 )* ( 5 - 3 )
12. + 9.8 * .98 * ( 10.0 / 3 )
__________________________________________
Here is infixCalculator:
import java.util.*;
public class InfixCalculator
{
private String infixExp;
private Stack opStack;//it can be any object in the stack
private Stack valStack;
public InfixCalculator(String exp)//this one will create two stack for you
{
infixExp=exp;
valStack = new Stack();
opStack = new Stack();
}
public double evaluate()
{
infixExp = "( " + infixExp + " )";
String[] tokens = infixExp.split("\s");//you're creating array for tokens
for(int i=0;i {
if(Character.isDigit(tokens[i].charAt(0)) || tokens[i].charAt(0)=='.'){
valStack.push(new Double(tokens[i]));
continue;
}
if (tokens[i].charAt(0)=='('){
opStack.push(new Character('('));
// continue;
}
else if (tokens[i].charAt(0)==')'){
while(opStack.peek().charValue()!='(')
execute();
opStack.pop();
// continue;
} else{
char ch1=tokens[i].charAt(0);
char ch2=opStack.peek().charValue();
if(precedence(ch1) > precedence(ch2))
opStack.push(new Character(ch1));
else {
while (precedence(ch1) <= precedence(opStack.peek().charValue()))
execute();
opStack.push(new Character(ch1));
}
}
}
return valStack.pop().doubleValue();
}
private int precedence(char ch)
{
switch(ch)
{
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
default:
return 1;
}
}
private void execute()
{
double result=0;
double op2=valStack.pop().doubleValue();
double op1=valStack.pop().doubleValue();
char op = opStack.pop().charValue();
switch(op)
{
case '*': result=op1 * op2;
break;
case '/': result=op1 / op2;
break;
case '+': result=op1 + op2;
break;
case '-': result=op1 - op2;
break;
}
valStack.push(new Double(result));
}
}
Modifier and Type Method and Description
boolean empty ()
Tests if this stack is empty.
E peek ()
Looks at the object at the top of this stack without removing it from the stack.
E pop ()
Removes the object at the top of this stack and returns that object as the value of this
function.
E push ( E item)
Pushes an item onto the top of this stack.
int search ( Object o)
Returns the 1-based position where an object is on this stack.
Explanation / Answer
Here is the completed code for the question. Post a comment in case of any issues, I shall respond. If happy with the answer, please rate it. Thank you.
Stage 1: Stack.java
package Lab17;
import java.util.ArrayList;
public class Stack<E> {
ArrayList<E> elements;
public Stack()
{
elements = new ArrayList<E>();
}
public boolean empty()
{
if(elements.size() == 0)
return true;
else
return false;
}
public E peek()
{
if(!empty())
return elements.get(elements.size()-1);
else
return null;
}
public E push(E val)
{
elements.add(val);
return val;
}
public E pop()
{
if(!empty())
return elements.remove(elements.size() - 1);
else
return null;
}
//returns the postion of the object from the top of stack, top is at position 1
public int search(Object o)
{
int idx = elements.indexOf(o);
return elements.size() - idx;
}
}
Stage 2: PostFix.java
package Lab17;
public class PostFix {
private Stack<Character> opStack;
private String postExp;
PostFix(){
opStack = new Stack<Character>();
postExp = new String();
}
public String convertToPostfix(String s) {
String postfix = "";
char ch, infix[] = s.toCharArray();
// Algorithm is same as InfixCalculator. Except,
for(int i = 0; i < infix.length; i++)
{
ch = infix[i];
if(Character.isSpaceChar(ch))
continue;
// if operand append to postExp
if(!isOperator(ch))
postfix+=ch;
// if op ( *,/,%,+,-) at to of stack has higher or equal precedency, then pop and
// append to postExp
else
{
if(ch == '(')
opStack.push('(');
else if(ch == ')')
{
while(!opStack.empty() && opStack.peek() != '(')
{
postfix += " " + opStack.pop() +" ";
}
if(!opStack.empty())
opStack.pop(); //pop (
}
else
{
while(!opStack.empty() && precedence(opStack.peek()) > precedence(ch))
{
postfix += " " + opStack.pop() + " ";
}
opStack.push(ch);
}
}
}
while(!opStack.empty())
postfix += " " + opStack.pop() ;
return postfix.replaceAll("(\s)+", " "); //replace multiple spaces by 1 spac character
}
private boolean isOperator(char ch)
{
if(ch == '(' || ch == ')' ||
ch == '+' || ch == '-' ||
ch == '/' || ch == '*' || ch == '%')
return true;
else
return false;
}
private int precedence(char op)
{
if(op == '(' || op == ')')
return 1;
else if(op == '+' || op =='-')
return 2;
else if(op == '/' || op == '*' || op == '%')
return 3;
else
return 0;
}
}
Stage 3: Lab17.java
package Lab17;
//driver progam to test PostFix class
public class Lab17 {
public static void main(String[] args) {
String expressions[] = { "(2 + 3 )* ( 5 - 3 )", "12. + 9.8 * .98 * ( 10.0 / 3 )"};
PostFix postfix = new PostFix();
for(int i = 0; i < expressions.length; i++)
{
System.out.println("Expression: " + expressions[i]);
System.out.println("Postfix: " + postfix.convertToPostfix(expressions[i]));
System.out.println(" ------------- ");
}
}
}
output
Expression: (2 + 3 )* ( 5 - 3 )
Postfix: 2 3 + 5 3 - *
-------------
Expression: 12. + 9.8 * .98 * ( 10.0 / 3 )
Postfix: 12. 9.8 .98 10.0 3 / * * +
-------------