evaluate an Infix expression, using the below algorithm AND this input expressio
ID: 3820560 • Letter: E
Question
evaluate an Infix expression, using the below algorithm AND this input expression: 11.1 + 22.2 * 3 / ( 1.1 + 5.5 )
ALGORITHM FOR EVALUATION THE INFIX EXPRESSION, USING the ArrayList OF Strings instance variable: (a void method with NO parameters)
// this is a variation of the infix eval. algorithm in the textbook
/*
declare a stack of String for the operators (use an ArrayStack, I'll call opStack)
declare a stack of Double for the operands (use a LinkedStack, I'll call valStack)
for each token in the ArrayList of strings (member variable)
if the token is an operator ("+", "-","*","/")
if opStack is empty
push token onto opStack
else if precedence(token) > precedence(top of opStack (call peek(), NOT pop))
push token onto opStack
else
while opStack isn't empty AND
precedence(token) <= precedence(top of opStack) (call peek(), NOT pop)
execute( opStack, valStack )
end while
push token onto opStack
end else
end else
else if token equals "("
push token onto opStack
else if token equals ")"
while top of opStack != "(" (peek, NOT pop)
execute(opStack, valStack)
end while
pop the opStack
else
convert the token to a Double value (if you don't know how, POST IN THE FORUM)
push the Double value onto the valStack
end else
end for loop
while( opStack isn't empty )
execute(opStack, valStack)
end while
if( valStack's size is 1 )
result = top of valStack
else
result = 0
endelse
End evaluate method
//-----------------------------------------------------------------------------
// WRITE MAIN as described on the assignment and using the following method & variable:
Explanation / Answer
import java.util.Stack;
public class Evaluation
{
public static double evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers
Stack<Double> operandStack = new Stack<>();
// Stack for Operators
Stack<Character> operatorStack = new Stack<Character>();
//using for is more natural here
for (int i = 0; i < tokens.length; i++)
{
if (tokens[i] == ' ')
continue;
// Token is a number, push it to stack
if (tokens[i] >= '0' && tokens[i] <= '9')
{
// There can be multi digit number. Create number as sring
StringBuffer numberString = new StringBuffer();
boolean isMultiDigit = false;
while (i < tokens.length && ((tokens[i] >= '0' && tokens[i] <= '9') || tokens[i] == '.'))
{
isMultiDigit = true;
numberString.append(tokens[i++]);
}
if(isMultiDigit)
{
i--;
}
// Converting numberString to integer and adding to array
operandStack.push(Double.parseDouble(numberString.toString()));
}
// Encounter open bracket, push it to operator stack
else if (tokens[i] == '(')
{
operatorStack.push(tokens[i]);
}
// Encounter closing bracket, evaluate and push result back in operand stack
else if (tokens[i] == ')')
{
while (operatorStack.peek() != '(')
{
double num1 = operandStack.pop();
double num2 = operandStack.pop();
operandStack.push(evaluateOpeartion(operatorStack.pop(), num1, num2));
}
operatorStack.pop();
}
// Encounter a operator
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/')
{
if(!operatorStack.empty() && operatorStack.peek() != '(')
{
while (!operatorStack.empty() &&
isHigherPrecedence(tokens[i], operatorStack.peek()))
{
operandStack.push(evaluateOpeartion(operatorStack.pop(), operandStack.pop(), operandStack.pop()));
}
}
// Push current token to 'ops'.
operatorStack.push(tokens[i]);
}
}
while (!operatorStack.empty())
operandStack.push(evaluateOpeartion(operatorStack.pop(), operandStack.pop(), operandStack.pop()));
// operandStack now contain result
return operandStack.pop();
}
// check for precendence order
public static boolean isHigherPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// Evaluate result of operator on operand b and a
public static double evaluateOpeartion(char op, double b, double 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;
}
// Test result
public static void main(String[] args)
{
System.out.println(Evaluation.evaluate("11.1 + 22.2 * 3/(1.1+5.5)"));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.