PART 1: Create a class called InfixCalculator which can be used to evaluate an i
ID: 3812761 • Letter: P
Question
PART 1: Create a class called InfixCalculator which can be used to evaluate an infix expression
Class InfixCalculator
{
private String infixExp;
private Stack opStack;
private Stack valStack;
public InfixCalculator(String exp)
{
infixExp = exp;
opStack = new Stack();
valStack = new Stack();
}
public double evaluate()
{
The algorithm uses two stacks: One stack, opStack, contains operators, and
The other stack, valStack, contains values of operands and intermediate
results. Note that the algorithm treats parentheses as operators with the
lowest precedency.
Add a “( “to beginning and “ )” to the end of the infixExp.
split the infixExp into array tokens
For (each token) do the following
If token is operand (first character ‘0’-’9’ or ‘.’) then valStack.push(token)
else If token is ‘(‘ then opStack.push(new Character(‘(‘));
else If token is ‘)’ then
do the following until matching ‘(‘ is found
execute()
opStack.pop()
else
token is an operator
if (precedence(ch)>precedence(top of opStack))
OpStack.push(ch)
else
{
while (precedence(ch)<=precedence(opStack.peek()))
execute()
opStack.push(ch)
}
END LOOP
return valStack.pop()
}
}
Note:
Execute() means
operand2 = valStack.pop()
operand1 = valStack.pop()
op = opStack.pop();
result = operand1 op operand2
valStack.push(result)
Infix expression can contain:
Blanks
Operands : double values
Operators : ( ) + - * /
Operator precedency
High 3: * /
2: + -
Low 1: ( )
PART 2: Write a driver program and evaluate the following expression using InfixCalculator class:
12. + 9.8 * .98 * ( 10.0 / 3 )
Explanation / Answer
//Part 1
import java.util.Stack;
public class InfixCalculator
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
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();
}
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()));
ops.push(tokens[i]);
}
}
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
return values.pop();
}
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
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;
}
//Part 2 Driver Method can be included in above part 1 program
public static void main(String[] args)
{
System.out.println(EvaluateString.evaluate("12. + 9.8 * .98 * (10.0 /3)");
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.