Can you please help me with this project? I have written the program that is giv
ID: 3600241 • Letter: C
Question
Can you please help me with this project? I have written the program that is giving me the result but i have used the stack class from java's library. i need to have my own stack class. Can you please write this program with own stack class? Thank you!
Program B – Expression Evaluation (80 points). A simple infix expression is one with no parentheses, e.g.
5 + 6 * 3
Using 2 stacks you can evaluate a simple infix expression in one pass without converting to a postfix form first. This requires use of two stacks, one with integers and one with operators. One way to do this is to use the approach in Program A, and instantiate two separate stacks for use in the main program.
The main program is again separate. The main program must implement the algorithm given below:
1.Create an empty operator stack
2.Create an empty value stack
3.Repeat
Get the next token.
If the token is:
A number:
Push the number onto the value stack.
An operator (call it thisOp):
While the operator stack is not empty, and the top item on the operator stack
has the same or greater precedence as thisOp,
Pop the operator from the operator stack.
Pop the value stack twice, getting two operands.
Apply the operator to the operands, in the correct order.
Push the result onto the value stack.
Push thisOp onto the operator stack.
until at the end of the string
4.While operator stack is not empty
Pop the operator from the operator stack.
Pop the value stack twice, getting two operands.
Apply the operator to the operands, in the correct order.
Push the result onto the value stack.
5.Pop result from value stack (at this point the operator stack should be empty).
You need only use integers for the operands, and +, -, and * for operators. You may use any material in the book. You must create your own stack class, either using arrays or your own linked list. The program must give an error message for an incorrectly formed expression. A GUI is not required; a simple console interface will suffice.
In the printed submission of your project you must at least include the 3 sample runs described below:
The following correct expression, 5+5 + 6*3 + 18
The following incorrect expression with an extra operator, 6+5 + * 6*3 + 18
The following incorrect expression with an extra operand, 6 6+5 * 3 + 18
Explanation / Answer
Hi, Please find my implementation.
You can take help from my code.
################
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 (empty()) 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 empty() { return root == null; }
// delete and return the most recently added element
public T peek() {
if (empty()) 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;
}
}
}
####################
public class ExpressionEvaluation
{
public static void evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
if(values.size() == 1)
System.out.println("value of the expression: "+values.pop());
else
System.out.println("Invalid expression");
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2)
{
if ((op1 == '*') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
}
return 0;
}
/*// Driver method to test above methods
public static void main(String[] args)
{
ExpressionEvaluation.evaluate("5+5 + 6*3 + 18");
}*/
}