Interpreter Design Pattern in Java: Before and after
Before
This is an adaptation of a design that appeared in a Pascal data structures book. The intent was to use stacks to convert normal "infix" syntax into "postfix" notation with operator precedence already handled.
public class InterpreterDemo {
public static boolean precedence(char a, char b) {
String high = "*/", low = "+-";
if (a == '(') {
return false;
}
if (a == ')' && b == '(') {
System.out.println(")-(");
return false;
}
if (b == '(') {
return false;
}
if (b == ')') {
return true;
}
if (high.indexOf(a) > - 1 && low.indexOf(b) > - 1) {
return true;
}
if (high.indexOf(a) > - 1 && high.indexOf(b) > - 1) {
return true;
}
//noinspection RedundantIfStatement
if (low.indexOf(a) > - 1 && low.indexOf(b) > - 1) {
return true;
}
return false;
}
public static String convertToPostfix(String expr) {
Stack<Character> operationsStack = new Stack<>();
StringBuilder out = new StringBuilder();
String operations = "+-*/()";
char topSymbol = '+';
boolean empty;
String[] tokens = expr.split(" ");
for (String token : tokens) {
if (operations.indexOf(token.charAt(0)) == -1) {
out.append(token);
out.append(' ');
} else {
while (!(empty = operationsStack.isEmpty()) &&
precedence(topSymbol = operationsStack.pop(), token.charAt(0))) {
out.append(topSymbol);
out.append(' ');
}
if (!empty) {
operationsStack.push(topSymbol);
}
if (empty || token.charAt(0) != ')') {
operationsStack.push(token.charAt(0));
} else {
topSymbol = operationsStack.pop();
}
}
}
while (!operationsStack.isEmpty()) {
out.append(operationsStack.pop());
out.append(' ');
}
return out.toString();
}
public static double processPostfix(String postfix, Map <String, Integer> map) {
Stack<Double> stack = new Stack<>();
String operations = "+-*/";
String[] tokens = postfix.split(" ");
for (String token : tokens) {
// If token is a number or variable
if (operations.indexOf(token.charAt(0)) == -1) {
double term;
try {
term = Double.parseDouble(token);
} catch (NumberFormatException ex) {
term = map.get(token);
}
stack.push(term);
// If token is an operator
} else {
double b = stack.pop(), a = stack.pop();
if (token.charAt(0) == '+') {
a = a + b;
}
if (token.charAt(0) == '-') {
a = a - b;
}
if (token.charAt(0) == '*') {
a = a * b;
}
if (token.charAt(0) == '/') {
a = a / b;
}
stack.push(a);
}
}
return stack.pop();
}
public static void main(String[] args) {
String infix = "C * 9 / 5 + 32";
String postfix = convertToPostfix(infix);
System.out.println("Infix: " + infix);
System.out.println("Postfix: " + postfix);
Map < String, Integer > map = new HashMap<>();
for (int i = 0; i <= 100; i += 10) {
map.put("C", i);
System.out.println("C is " + i + ", F is " + processPostfix(postfix, map));
}
}
}
Output
Infix: C * 9 / 5 + 32 Postfix: C 9 * 5 / 32 + C is 0, F is 32.0 C is 10, F is 50.0 C is 20, F is 68.0 C is 30, F is 86.0 C is 40, F is 104.0 C is 50, F is 122.0 C is 60, F is 140.0 C is 70, F is 158.0 C is 80, F is 176.0 C is 90, F is 194.0 C is 100, F is 212.0
After
This is a refactoring that follows the intent of the Interpreter design pattern. All classes in the Operand hierarchy: implement the evaluate(context), digest some piece of the context argument, and return their contribution to the recursive traversal. Applying the Interpreter pattern in this domain is probably inappropriate.
interface Operand {
double evaluate(Map<String, Integer> context);
void traverse(int level);
}
class Expression implements Operand {
private char operation;
public Operand left, right;
public Expression(char operation) {
this.operation = operation;
}
public void traverse(int level) {
left.traverse(level + 1);
System.out.print("" + level + operation + level + " ");
right.traverse(level + 1);
}
public double evaluate(Map<String, Integer> context) {
double result = 0;
double a = left.evaluate(context);
double b = right.evaluate(context);
if (operation == '+') {
result = a + b;
}
if (operation == '-') {
result = a - b;
}
if (operation == '*') {
result = a * b;
}
if (operation == '/') {
result = a / b;
}
return result;
}
}
class Variable implements Operand {
private String name;
public Variable(String name) {
this.name = name;
}
public void traverse(int level) {
System.out.print(name + " ");
}
public double evaluate(Map<String, Integer> context) {
return context.get(name);
}
}
class Number implements Operand {
private double value;
public Number(double value) {
this.value = value;
}
public void traverse(int level) {
System.out.print(value + " ");
}
public double evaluate(Map context) {
return value;
}
}
public class InterpreterDemo {
public static com.sourcemaking.interpretator.first_example.before.InterpreterDemo interpreter
= new com.sourcemaking.interpretator.first_example.before.InterpreterDemo();
public static String convertToPostfix(String expr) {
Stack<Character> operationsStack = new Stack<>();
StringBuilder out = new StringBuilder();
String operations = "+-*/()";
char topSymbol = '+';
boolean empty;
String[] tokens = expr.split(" ");
for (String token : tokens)
if (operations.indexOf(token.charAt(0)) == -1) {
out.append(token);
out.append(' ');
} else {
while (!(empty = operationsStack.isEmpty()) && interpreter.precedence(topSymbol =
operationsStack.pop(), token.charAt(0))) {
out.append(topSymbol);
out.append(' ');
}
if (!empty) {
operationsStack.push(topSymbol);
}
if (empty || token.charAt(0) != ')') {
operationsStack.push(token.charAt(0));
} else {
topSymbol = operationsStack.pop();
}
}
while (!operationsStack.isEmpty()) {
out.append(operationsStack.pop());
out.append(' ');
}
return out.toString();
}
public static Operand buildSyntaxTree(String tree) {
Stack <Operand> stack = new Stack<>();
String operations = "+-*/";
String[] tokens = tree.split(" ");
for (String token : tokens)
if (operations.indexOf(token.charAt(0)) == -1) {
Operand term;
try {
term = new Number(Double.parseDouble(token));
} catch (NumberFormatException ex) {
term = new Variable(token);
}
stack.push(term);
// If token is an operator
} else {
Expression expr = new Expression(token.charAt(0));
expr.right = stack.pop();
expr.left = stack.pop();
stack.push(expr);
}
return stack.pop();
}
public static void main(String[] args) {
System.out.println("celsius * 9 / 5 + thirty");
String postfix = convertToPostfix("celsius * 9 / 5 + thirty");
System.out.println(postfix);
Operand expr = buildSyntaxTree(postfix);
expr.traverse(1);
System.out.println();
HashMap < String, Integer > map = new HashMap<>();
map.put("thirty", 30);
for (int i = 0; i <= 100; i += 10) {
map.put("celsius", i);
System.out.println("C is " + i + ", F is " + expr.evaluate(map));
}
}
}
Output
celsi * 9 / 5 + thirty celsi 9 * 5 / thirty + celsi 3*3 9.0 2/2 5.0 1+1 thirty C is 0, F is 30.0 C is 10, F is 48.0 C is 20, F is 66.0 C is 30, F is 84.0 C is 40, F is 102.0 C is 50, F is 120.0 C is 60, F is 138.0 C is 70, F is 156.0 C is 80, F is 174.0 C is 90, F is 192.0 C is 100, F is 210.0
Support our free website and own the eBook!
- 22 design patterns and 8 principles explained in depth
- 406 well-structured, easy to read, jargon-free pages
- 228 clear and helpful illustrations and diagrams
- An archive with code examples in 4 languages
- All devices supported: EPUB/MOBI/PDF formats