You will implement an infix arithmetic expression evaluator, as described in the
ID: 3742724 • Letter: Y
Question
You will implement an infix arithmetic expression evaluator, as described in the lecture slides, using a stack template that you implement in Java. You must implement your own stack template and not use an existing template.
Stack
Write the methods in the template provided that are needed to compile and pass the tests.
The input is infix arithmetic expressions, one per line, so think about how you want to manage the
input.
Expression Evaluator
The following operators, and no others, will appear in the infix expressions. Note that parentheses,
in various forms, are appropriately categorized as operators. More about that below.
+ Addition
- Subtraction
* Multiplication
/ Division
^ Exponentiation (power)
sin and cos
Trigonometric functions that take arguments in radians, not degrees
log Natural logarithm (base e)
( ), { }, [ ] Parentheses in three forms
The space character, “ ”, is used as a delimiter to separate tokens in the input. This means that
operators and operands are going to be separated from each other by a space.
( 3 + 5 ) is a valid expression
( 3 + 5) is not a valid expression because there is no space between the operand, 5, and the right
parenthesis.
The input type is float (double) so a number such as 3.5 is a valid operand input.
So that you know to expect this, there may be cases where the expression includes a divide
operator with a denominator operand equal to zero. Java and computer hardware follow the IEEE
754 standard for computer arithmetic on floating point values. Thus, in cases of divide-by-zero,
the double type output will be a positive or a negative infinity.
A correctly formatted infix expression will include one or more parenthesis pair(s) that directly
enclose each operation and its operands or its operand (for the log operation). Individual
operands may also be enclosed in one or more parenthesis pairs. For example,
• 3 + 5 is not valid because there is no enclosing parenthesis pair
• ( { 3 } + 5 ) is a valid expression because an operand may be enclosed or not enclosed
by one parenthesis pair and there is one pair enclosing the + operator and its operands
• ( { 3 } + 5 } is not valid because the outer parenthesis pair does not match as to symbol
used
• ( log 3 ) is a valid expression, ( log ( 3 ) ) is a valid expression and both evaluate to
1.0986122886681098
• { ( cos ( ( 90 ) + [ [ [ 5 ] ] ] ) ) } is a valid expression that evaluates to
0.7301735609948197
In addition to correctly evaluating correctly formatted infix expressions, your program should
reject incorrectly formatted infix expressions. Incorrect formatting includes the following
situations only.
• An empty pair of parentheses, e.g., { }, which does not enclose either an operand alone
or a pair of operands with an infix-positioned operator
• Mismatched parenthesis pair type, e.g., ( paired with } as in ( 3 + 5 }
• Mismatched parenthesis pair orientation, e.g., ( paired with ( as in ( 3 + 5 (
• An incorrectly formatted operand, e.g., 7.8k7o
Your program should print “Invalid expression” in response to an input line that contains any of
these errors. It is acceptable to end effort for evaluating an expression as soon as a formatting
error is detected.
To detect invalid formatting you should treat parenthesis symbols as you do other operators
with respect to storing them in a stack. Error detection will also require care in matching
parenthesis symbols and in determining what token, if any, is contained within a parenthesis
pair. Detecting malformed operands can be accomplished by checking for a
NumberFormatException
No inverse Trignometric function used
Input : ( 3 + [ 4 + 5 ] ) Output :12
Input : { 2 / ( 5 - 5 ) } Output :Infinity
Input : { 42 + [ 87 / ( { 3 - 9 } * 56 ) ] } Output : 41.74107142857143
Input : ( 3 + 5.8k2o ) Ouput : Invalid
Input : ( sin ( log ( 3.1 ^ 3 ) ) ) Ouput : -0.24993553919734932
Explanation / Answer
import java.util.Stack;
public class EvaluateString
{
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("100 * ( 2 + 12 )"));
System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.