Evaluate Arithmetic Expressions Requirements: Implement a concrete ArrayStack cl
ID: 3914328 • Letter: E
Question
Evaluate Arithmetic Expressions
Requirements:
Implement a concrete ArrayStack class that extends the Stack interface as we discussed in the class (any other different Stack class implementation, even if it is implemented by yourself, will not receive any credit).
Write a method that evaluates an arithmetic expression, which is given by a string. Evaluate should prompt for user input and then give an answer to the expression.
Your implementation is required to use the Stack interface we discussed in the class. Implementation formats are given below. You could make slight modifications but make sure format is followed.
Write a necessary test program to verify the result. For example,
You may want to test all possible corner conditions to make sure your implement is inclusive.
Your implementation only considers +, - and * operators and does not need to consider parentheses.
Implementation should support parentheses. For example:
Stack implementation format to be used
public interface stack {
boolean isEmpty();
boolean isFull();
int size(); //this should return number of data elements
void push (Object item);
Object pop();
Object top();
}
public interfact stack {
boolean isEmpty();
boolean isFull();
int size(); //this should return number of data elements
void push (Object item);
Object pop();
Object top();
}
Array implementation Format to be used
***************************
size()
return k+1
isEmpty()
return k==-1
isFull
return k==CAP-1
------------------
pop()
if (isEmpty()) then
retun null;
else
k=k-1
return Array[k+1]
-------------------
push()
if (isFull()) then
throw SomeException
else
Array[k] --- item
-------------------
top()
if (isEmpty()) then
return null
else
return Array[k];
Explanation / Answer
import java.util.Scanner;
import java.util.Stack;
public class ArrayStack extends Stack
{
public static int expression(String str)
{
ArrayStack obj=new ArrayStack();
char[] tokens = str.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 str 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)
{
Scanner sc=new Scanner(System.in);
System.out.print("Enter an expression :");
String input=sc.nextLine();
System.out.println("Result ="+ArrayStack.expression(input));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.