As a Client , lets use a unit test. I show the test method only:

	@Test
	public void testParsing5Sums() {
		NExpression expression = parser.parse("((1.23 + 2.5) + (6 + (0.55 * 5.36)))");
		assertEquals("[([[([1.23] + [2.5])]] + [[([6] + [[([0.55] * [5.36])]])]])]", expression.toStructuredString());
		BigDecimal result = expression.calculate(new NCalculationContext());
		assertNotNull(result);
		assertEquals(new BigDecimal("12.678"), result);
	}

The toStructuredString() method is mainly there to test and visualize the structure of the expression tree.

The root class in the hierarchy, NExpression , fulfills the role of AbstractExpression in the original pattern.

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;


public abstract class NExpression {
	public abstract BigDecimal calculate(NCalculationContext context);

	public static NExpression parse(String text) {
		NExpressionParser parser = new NExpressionParser();
		return parser.parse(text);
	}

	public abstract String toStructuredString();

	public String toString() {
		return toStructuredString();
	}

	public abstract boolean isTerminal();

	public boolean isOperation() {
		return false;
	}

	public boolean isParentheses() {
		return false;
	}

	public NOperation asOperation() {
		throw new ClassCastException("Not an operation");
	}

	public NParentheses asParentheses() {
		throw new ClassCastException("Not parentheses");
	}
}

The terminal expression is reduced to an abstract class:

package be.ooxs.examples.designpatterns.interpreter;

public abstract class NTerminalExpression extends NExpression {

	@Override
	public boolean isTerminal() {
		return true;
	}

}

And the non terminal expression is very similar:

package be.ooxs.examples.designpatterns.interpreter;

public abstract class NNonTerminalExpression extends NExpression {

	@Override
	public boolean isTerminal() {
		return false;
	}
}

A constant is a terminal expression and represents a decimal number literal.

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;

public class NConstant extends NTerminalExpression {
	private BigDecimal value = BigDecimal.ZERO;

	public BigDecimal getValue() {
		return value;
	}

	public void setValue(BigDecimal value) {
		this.value = value;
	}

	@Override
	public BigDecimal calculate(NCalculationContext context) {
		return getValue();
	}

	public String toStructuredString() {
		return value.toPlainString();
	}
}

A parameter is bound to a value via its name, when the calculation method is invoked. It is the responsibility of the client to provide a value.

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;

public class NParameter extends NTerminalExpression {
	private String name;

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public BigDecimal calculate(NCalculationContext context) {
		return context.value(name);//TODO throw an IllegalArgumentException when there is no value for the name
	}

	public String toStructuredString() {
		return name;
	}
}

The NOperation class has a left and a right operand, so it does not allow for things like '1 + 2 + 3 + 4' and is strictly limited to two children.

Note the isOperation() and asOperation() methods, which are used to make the code a little more elegant in the parser - it is meant to eliminate 'instanceof' combined with a cast.

package be.ooxs.examples.designpatterns.interpreter;

public abstract class NOperation extends NNonTerminalExpression {
	private NExpression left;
	private NExpression right;

	public NExpression getLeft() {
		return left;
	}

	public void setLeft(NExpression left) {
		this.left = left;
	}

	public NExpression getRight() {
		return right;
	}

	public void setRight(NExpression right) {
		this.right = right;
	}

	@Override
	public final String toStructuredString() {
		String leftStructuredString = left == null ? "empty" : getLeft().toStructuredString();
		String rightStructuredString = right == null ? "empty" : getRight().toStructuredString();

		StringBuilder buffer = new StringBuilder().append("[").append(leftStructuredString).append("]");
		buffer.append(" ").append(getSymbol()).append(" ");
		buffer.append("[").append(rightStructuredString).append("]");
		return buffer.toString();
	}

	protected abstract String getSymbol();

	@Override
	public NOperation asOperation() {
		return this;
	}

	@Override
	public boolean isOperation() {
		return true;
	}
}

The actual '+' operation is very simple:

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;

public class NSum extends NOperation {

	@Override
	public BigDecimal calculate(NCalculationContext context) {
		return getLeft().calculate(context).add(getRight().calculate(context));
	}

	@Override
	protected String getSymbol() {
		return "+";
	}

}

And '*' is very similar. '/' and '-' are left as an exercise for the reader...

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;

public class NProduct extends NOperation {

	@Override
	public BigDecimal calculate(NCalculationContext context) {
		return getLeft().calculate(context).multiply(getRight().calculate(context));
	}

	@Override
	protected String getSymbol() {
		return "*";
	}

}

Parentheses contain a single other expression as a child and is different in that respect compared to the operations.

It is primarily needed during parsing...

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;

public class NParentheses extends NNonTerminalExpression {
	private NExpression expression;

	public NExpression getExpression() {
		return expression;
	}

	public void setExpression(NExpression expression) {
		this.expression = expression;
	}

	@Override
	public BigDecimal calculate(NCalculationContext context) {
		return expression.calculate(context);
	}

	@Override
	public String toStructuredString() {
		String structuredString = expression == null ? "empty" : expression.toStructuredString();

		return "[(" + structuredString + ")]";
	}

	@Override
	public NParentheses asParentheses() {
		return this;
	}

	@Override
	public boolean isParentheses() {
		return true;
	}

}

The parser is the most complex part of this example, but it is not a part of the design pattern. You can safely ignore it as long as you remember it transforms a String like "(x1 * x1) + (x2 * x2)" into the 9 instances of different concrete subclasses of NExpression and that it returns the NSum instance.

The parser does not respect conventional precedence of the operations, it will treat 4 + 2 * 3 as (4 + 2) * 3 and not as 4 + (2 * 3) as we all learned a few years ago. Resulting in 18 instead of 24.

This parser uses regular expressions to obtain each token and then calls handleExpression . This method creates the corresponding NExpression instance and then pushes it on a stack. In between, operations tkae the previous expression on the stack as the left operand and parentheses take the previous expression when they are closed. The right operand for an operation is taken before it is pushed on the stack (in the assign() method.)

Perhaps it is easier for some to see what happens when running ((1.23 + 2.5) + (6 + (0.55 * 5.36))) through the parser. This is the output of the two System.out.println(...) statements in the code, showing the token and then the contents of the stack:

parsing: ((1.23 + 2.5) + (6 + (0.55 * 5.36)))
(		##	[[(empty)], [(empty)]]
(		##	[[(empty)], [(empty)], [(empty)], [(empty)]]
1.23		##	[[(empty)], [(empty)], [(empty)], [(empty)], 1.23]
+		##	[[(empty)], [(empty)], [(empty)], [(empty)], [1.23] + [empty]]
2.5		##	[[(empty)], [(empty)], [(empty)], [(empty)], [1.23] + [2.5]]
)		##	[[(empty)], [(empty)], [([1.23] + [2.5])]]
+		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [empty]]
(		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)]]
6		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], 6]
+		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [empty]]
(		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [[(empty)]], [(empty)]]
0.55		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [[(empty)]], [(empty)], 0.55]
*		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [[(empty)]], [(empty)], [0.55] * [empty]]
5.36		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [[(empty)]], [(empty)], [0.55] * [5.36]]
)		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[(empty)]], [(empty)], [6] + [[([0.55] * [5.36])]]]
)		##	[[(empty)], [(empty)], [[([1.23] + [2.5])]] + [[([6] + [[([0.55] * [5.36])]])]]]
)		##	[[([[([1.23] + [2.5])]] + [[([6] + [[([0.55] * [5.36])]])]])]]

And here is the actual code for the parser:

package be.ooxs.examples.designpatterns.interpreter;

import java.math.BigDecimal;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class NExpressionParser {

	public static NExpressionParser createInstance() {
		return new NExpressionParser();
	}

	public NExpression parse(String text) {
		String regex = "\\s*(";
		regex += "([-+]?\\d+([.]\\d+)?)";//numerical value
		regex += "|([a-zA-Z]\\w*)";//parameter name
		regex += "|(\\()";// a '('
		regex += "|(\\))";// a ')'
		regex += "|(([-+*/])))\\s*";// an operator -+/*
		Pattern pattern = Pattern.compile(regex);
		Matcher matcher = pattern.matcher(text);
		System.out.println("parsing: " + text);
		NExpression rootExpression = null;
		Stack<NExpression> expressions = new Stack<NExpression>();
		while (matcher.find()) {
			String currentToken = matcher.group(1);
			String numericalValue = matcher.group(2);
			;
			String parameterName = matcher.group(4);
			String openParentheses = matcher.group(5);
			String closeParentheses = matcher.group(6);
			String operator = matcher.group(7);

			handleExpression(expressions, currentToken, numericalValue, parameterName, openParentheses, closeParentheses, operator);
		}
		rootExpression = expressions.pop();
		return rootExpression;
	}

	/**
	 * This method exists for the unit tests and avoids having to call
	 * {@link #handleExpression(Stack, String, String, String, String, String, String)}
	 * with the same string for the description parameter and one of the other
	 * parameters like this: parser.handleExpressionForUnitTesting(expressions,
	 * "(", null, null, "(", null, null); which could easily lead to mistakes in
	 * the unit tests.
	 */
	protected void handleExpressionForUnitTesting(Stack<NExpression> expressions, String numericalValue, String parameterName, String openParentheses,
			String closeParentheses, String operator) {
		String description = "undetermined";

		if (numericalValue != null) {
			description = numericalValue;
		} else if (parameterName != null) {
			description = parameterName;
		} else if (operator != null) {
			description = operator;
		} else if (openParentheses != null) {
			description = openParentheses;
		} else if (closeParentheses != null) {
			description = closeParentheses;
		}
		handleExpression(expressions, description, numericalValue, parameterName, openParentheses, closeParentheses, operator);
	}

	protected void handleExpression(Stack<NExpression> expressions, String description, String numericalValue, String parameterName, String openParentheses,
			String closeParentheses, String operator) {
		if (numericalValue != null) {
			NConstant constant = new NConstant();
			constant.setValue(new BigDecimal(numericalValue));
			assign(expressions, constant);
		} else if (parameterName != null) {
			NParameter parameter = new NParameter();
			parameter.setName(parameterName);

			assign(expressions, parameter);
		} else if (operator != null) {
			NOperation operation = null;
			if ("+".equals(operator)) {
				operation = new NSum();
			} else if ("*".equals(operator)) {
				operation = new NProduct();
			}//TODO implement other operations like - and /
			operation.setLeft(expressions.pop());

			assign(expressions, operation);
		} else if (openParentheses != null) {
			NParentheses parentheses = new NParentheses();
			assign(expressions, parentheses);
			expressions.push(parentheses);
		} else if (closeParentheses != null) {
			NExpression expression = expressions.pop();
			NExpression previous = expressions.pop();
			if (previous.isOperation()) {
				NOperation operation = previous.asOperation();
				operation.setRight(expression);
			} else if (previous.isParentheses()) {
				NParentheses parentheses = previous.asParentheses();
				parentheses.setExpression(expression);
			} else {
				throw new IllegalStateException("duh");
			}
		}
		System.out.println(description + "\t\t##\t" + expressions);
	}

	private void assign(Stack<NExpression> expressions, NExpression expression) {
		if (!expressions.isEmpty()) {
			NExpression top = expressions.peek();
			if (!top.isTerminal()) {
				if (top instanceof NOperation) {
					((NOperation) top).setRight(expression);
				} else {
					expressions.push(expression);
				}
			} else {
				throw new IllegalStateException("Expect non terminal expression as parent");
			}
		} else {
			expressions.push(expression);
		}
	}
}