Expression Evaluator in java
It is a concept which deals with parsing , operator precedence, parenthesis handling. Let us implement this in java using Stack concept.
As everyone knows, Stack is a data structure with Last in
First Out concept.
Consider the following statement.
8 + 5 * (4 - 3)
Where
(4-3) -parenthesis
+,*,- deals with
Operator precedence.
Parsing is done using stacks for expression evaluation.
Java Implementation:
- There are three methods(‘eval()’,’isOperator()’ and ‘applyOp()’).
- The ‘eval()’ function separates value and operator separately.
- Based on the expression, operator precedence and parenthesis, it executes the expression.
- ‘isOperator()’ checks it is a operator or not.
- ‘applyOp()’ is for operator execution.
- ‘main()’ deals with creating objects for the class and call the function ‘eval()’ to get the output.
Program:
import java.util.*;
import java.util.Stack;
public class ExprEvaluator {
public static int
eval(String expr) {
Stack<Integer> s_value = new Stack<>();
Stack<Character> s_oper = new Stack<>();
for (int i = 0;
i < expr.length(); i++) {
char ch =
expr.charAt(i);
if
(Character.isWhitespace(ch)) continue;
if (Character.isDigit(ch)) {
int n
= 0;
while
(i < expr.length() && Character.isDigit(expr.charAt(i))) {
n
= n * 10 + (expr.charAt(i) - '0');
i++;
}
i--;
s_value.push(n);
}
else if
(ch == '(') {
s_oper.push(ch);
}
else if
(ch == ')') {
while
(s_oper.peek() != '(') {
s_value.push(applyOp(s_oper.pop(), s_value.pop(), s_value.pop()));
}
s_oper.pop(); // remove '('
}
else if
(isOperator(ch)) {
while
(!s_oper.isEmpty() && precedence(ch) <= precedence(s_oper.peek())) {
s_value.push(applyOp(s_oper.pop(), s_value.pop(), s_value.pop()));
}
s_oper.push(ch);
}
}
while
(!s_oper.isEmpty()) {
s_value.push(applyOp(s_oper.pop(), s_value.pop(), s_value.pop()));
}
return
s_value.pop();
}
private static
boolean isOperator(char ch) {
return ch ==
'+' || ch == '-' || ch == '*' || ch == '/';
}
private static int
precedence(char op) {
if (op == '+'
|| op == '-') return 1;
if (op == '*'
|| op == '/') return 2;
return 0;
}
private static int
applyOp(char op, int b, int a) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
return 0;
}
public static void
main(String[] args) {
String expr =
"8 + 5 * (4 - 3)";
System.out.println("Result of the expression "+expr+"
is:" + eval(expr));
}
}
Output:
C:\raji\blog>javac ExprEvaluator.java
C:\raji\blog>java ExprEvaluator
Result of the expression 8 + 5 * (4 - 3) is:13
This is the way of creating Expression Evaluator in java.
Hope, you understands it. Keep Coding!!!
Comments
Post a Comment