Here is the question from my friend (ex-colleague):
“I have a mathematical expression say (45 %2B ((4 – 25) %2B 2)) as a string. How can you evaluate it to find the result using JAVA programming language?”
Well, this is very easy with javascript as it has the powerful eval() function. But java is static, strongly typed, not-that-flexible language. So, this cannot be provided as a language feature which leads me to either search for some available libraries or, write my won little library. If you are reading this post, you know by now what my decision was:) Come on, what’s fun in searching for someone’s work ;) (Well, not always)
So, here it is… This would have been much simpler with dynamic language like Groovy… But, the requirement clearly said JAVA
Logic is quite simple. The given input is an infix expression. Use stack and keep pushing all the elements (including braces) till you encounter a closed brace. Now, popping from the stack till you encounter an open brace will get you an operator and 2 operands. Evaluate it and push back the result to continue the same logic till the end of the input string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.rs.utils;
import java.util.ArrayList;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Evaluator {
public static int eval(String infixExpression) {
Stack<String> stack = new Stack<String>();
String trimmedExp = infixExpression.replaceAll(" ", "");
for (String c : split(trimmedExp)) {
if (")".equals(c)) {
if (!"(".equals(stack.peek())) {
String result = performOperation(stack.pop(), stack.pop(),
stack.pop()) + "";
stack.pop(); // remove also the open bracket
stack.push(result);
}
} else {
stack.push(c);
}
}
return Integer.parseInt(stack.pop());
}
private static int performOperation(String operand2, String operator,
String operand1) {
int op1 = Integer.parseInt(operand1);
int op2 = Integer.parseInt(operand2);
switch (operator.toCharArray()[0]) {
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
default: return 0;
}
}
static String[] split(String exp) {
ArrayList<String> parts = new ArrayList<String>();
Pattern pat = Pattern.compile("\\d++|\\+|\\-|\\*|/|\\(|\\)");
Matcher matcher = pat.matcher(exp);
while (matcher.find()) {
parts.add(matcher.group());
}
return parts.toArray(new String[0]);
}
}