Evaluate String Expression Java | InFix Expression Evaluation Java
Evaluate an expression represented by a String
The expression can contain parentheses, you can assume parentheses are well-matched. For simplicity, you can assume only binary operations allowed are +, -, *, and /.
Infix Notation: Operators are written between the operands they operate on, e.g. 3 + 4.
Input: 100 * ( 2 + 12 )
Output: 1400
Algorithm:
- While there are still tokens to be read in,
1.1 Get the next token.
1.2 If the token is:
1.2.1 A number: push it onto the value stack.
1.2.2 A variable: get its value, and push onto the value stack.
1.2.3 A left parenthesis: push it onto the operator stack.
1.2.4 A right parenthesis:
1 While the thing on top of the operator stack is not a
left parenthesis,
1 Pop the operator from the operator stack.
2 Pop the value stack twice, getting two operands.
3 Apply the operator to the operands, in the correct order.
4 Push the result onto the value stack.
2 Pop the left parenthesis from the operator stack, and discard it.
1.2.5 An operator (call it thisOp):
1 While the operator stack is not empty, and the top thing on the
operator stack has the same or greater precedence as thisOp,
1 Pop the operator from the operator stack.
2 Pop the value stack twice, getting two operands.
3 Apply the operator to the operands, in the correct order.
4 Push the result onto the value stack.
2 Push thisOp onto the operator stack. - While the operator stack is not empty,
1 Pop the operator from the operator stack.
2 Pop the value stack twice, getting two operands.
3 Apply the operator to the operands, in the correct order.
4 Push the result onto the value stack. - At this point the operator stack should be empty, and the value
stack should have only one value in it, which is the final result.
Advertisement
/* A Java program to evaluate a given expression where tokens are separated by space.*/
import java.util.Stack;
public class EvaluateString
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
String operators = "+-*/";
// 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 (Character.isDigit(tokens[i]))
{
StringBuffer valueBuffer = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && Character.isDigit(tokens[i]))
valueBuffer.append(tokens[i++]);
values.push(Integer.parseInt(valueBuffer.toString()));
// As we have move pointer ahead we need to move it back once
i--;
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
// Closing brace encountered, let's solve entire brace by poping out elements from ops and values till we get opening bracket
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 (operators.indexOf(tokens[i])!=-1)
{
// 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;
return true;
}
// A utility method to apply an operator to operand a and b
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("10 + 2 * 6"));
System.out.println(EvaluateString.
evaluate("100 * 2 + 12"));
System.out.println(EvaluateString.
evaluate("100 * ( 2 + 12 )"));
System.out.println(EvaluateString.
evaluate("0 * ( 2 + 12 ) / 1"));
}
}
Advertisement