Part 1 is done: import java.util.List; import java.util.ArrayList; public class
ID: 3726985 • Letter: P
Question
Part 1 is done:
import java.util.List;
import java.util.ArrayList;
public class MyStack
{
ArrayList<Integer> T = new ArrayList<Integer>();
public MyStack()
{
}
public void push(int i)
{
T.add(0,i);
}
public void pop()
{ int sz=T.size();
T.remove(sz-1);
}
public int lookUp()
{
int sz=T.size();
int i=T.get(sz-1);
return i;
}
public boolean isEmpty()
{
T.isEmpty();
return true;
}
void display()
{
System.out.println(T);
}
Part 2:
Write the MathCalculator class to evaluate arithmetic expressions; it will make use of the generic stack class defined in part a.
Assume the following regarding the expression to evaluate:
all numbers are integers
the possible arithmetic operators are +, -, *, /, % and ^ where ^ is used for exponent
there may or may not be spaces between the operators, numbers and brackets
The minus sign always represents a subtraction; there is no unary minus sign in the expression. The result of a calculation may yield a negative number
there will not be any division by zero
The operators have the following priority of evaluation:
Highest priority ^
* / %
Lowest priority + -
It is important to know that:
operators of equal priority are evaluated from left to right
order of evaluation can be altered using brackets
the result of any operation is integer, including division.
The class will have 2 data members:
A String to store the arithmetic expression
An integer to store the result of the evaluation of the expression
The class should have the following public methods:
A zero-parameter constructor to set the arithmetic expression to the null String (“”) and the result to zero
void evaluate (String) method to evaluate the given arithmetic expression (parameter) to obtain the result. Make sure to add a blank at the end of the given String before you start processing it.
String toString() returns the arithmetic expression followed by the equal sign and then the result. For example:
3 * 6 + ( 25 - 7 * 2 ) / 10 = 19
The evaluation of the arithmetic expression must be done according to the specifications below:
Evaluate as you process the string from left to right, taking into consideration the priority of operator and brackets, making use of an Integer stack and a Character stack.
Only go through the String with the arithmetic expression once.
Code private methods to efficiently produce the result. Methods (private or public) should not have more than 50 or 60 lines of code.
Explanation / Answer
Part:-1
package chegg;
import java.util.List;
import java.util.ArrayList;
public class Mystack
{
ArrayList<Integer> T = new ArrayList<Integer>();
public Mystack()
{
}
public void push(int i)
{
T.add(0,i);
}
public void pop()
{ int sz=T.size();
T.remove(sz-1);
}
public int lookUp()
{
int sz=T.size();
int i=T.get(sz-1);
return sz;
}
public boolean isEmpty()
{
T.isEmpty();
return true;
}
void display()
{
System.out.println(T);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Mystack ob =new Mystack();
ob.push(51);
ob.push(74);
ob.push(95);
ob.pop();
System.out.println(ob.lookUp());
System.out.println(ob.isEmpty());
ob.display();
}
}
Output:-
2
true
[95, 74]
Part 2:-
import java.util.Stack;
public class MathCalculator
{
public static int 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 opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
while (ops.peek() != '(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
// Current token is an operator.
else if (tokens[i] == '+' || 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
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || 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;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
// Driver method to test above methods
public static void main(String[] args)
{
System.out.println(EvaluateString.evaluate("10 + 2 * 6"));
System.out.println(EvaluateString.evaluate("100 * 2 + 12"));
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}