Arithmetic Expression Evaluator- WITHOUT Stacks! Recursive Program The purpose o
ID: 3733976 • Letter: A
Question
Arithmetic Expression Evaluator- WITHOUT Stacks! Recursive Program
The purpose of this project is to gain an understanding of using recursion to solve problems.
Write a Java application or applet that asks a user to enter an arithmetic expression, and then compute and print out the result. The expression may contain parenthesis, *, /, +, - and numbers. Unary plus and minus do not need to be supported. Normal Java evaluation precedence should be used. For example:
(1 + 2) * (6 / 2 + 3) = 18
BNF (Backus-Naur Form) is commonly used in compilers to describe the language to be accepted. A BNF definition of an arithmetic expression is:
<expression> ::= <term> + <expression> |
<term> - <expression> |
<term>
<term> ::= <factor> * <term> |
<factor> / <term> |
<factor>
<factor> ::= {<expression>) |
<float> |
<int>
You may use the above BNF definition as a basis for your implementation. (I would prefer the answer to use this!!) The BNF definition should show you how to call the various functions recursively if you name your functions expression, term and factor.
The solution is to use normal recursion. That is, have the following procedures: expression, term, and factor. You call expression first. It always calls term (based on the BNF description). Upon return it checks for a + or – or end of expression string. In the case of + or – it calls expression (recursively) (based on the BNF description) and then does the addition or subtraction.
You do the same for term and factor following the BNF description.
You don’t need any stacks. Just use normal Java recursion calling : expression, term, and factor based on the BNF description.
Hope this helps!!
Explanation / Answer
Code:
public class ExpressionEval
{
//////////////////// Main method /////////////////////////////////////
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Please enter expression to evaluate");
String expr = sc.nextLine();
System.out.println(ExpressionEval.evaluate(expr));
}
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
//////////////////// Initialise stack for integer values ///////////////////////////
Stack<Integer> values = new Stack<Integer>();
//////////////////// Initialise stack for operator values ///////////////////////////
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++)
{
if (tokens[i] == ' ')
continue;
if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
else if (tokens[i] == '(')
ops.push(tokens[i]);
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 (!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()));
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;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.