Definition
Clean Design of Stack
By definition minimum set of stack operations are push & pop.To represent this fundamental definition, most appropriate design in Java is an interface with these two operations
package clean.project.ds.stack.contract;
public interface PrimitiveStack <T> {
public void push(T item) throws Exception;
public T pop() throws Exception;
}
As this is an abstract data type and the set of operations define a stack, using interface is most appropriate.
Due to practical requirements, additional operations may be required for the stack. Since these additional operations are optional and may not be required always, hence following the Interface Segregation Principle, we can define interfaces which expand the PrimitiveStack definition
package clean.project.ds.stack.contract;
public interface LimitedStack<T> extends PrimitiveStack<T> {
public boolean isEmpty();
public boolean isFull();
}
package clean.project.ds.stack.contract;
public interface MonitoredStack<T> extends PrimitiveStack<T> {
public T peek() throws Exception;
}
package clean.project.ds.stack.contract;
public interface MonitoredLimitedStack<T> extends LimitedStack<T> {
public T peek() throws Exception;
}
For future extensibility, we can extend any of the interfaces to define new interfaces for any future requirements.
These interfaces can be implemented by the concrete classes. This creates a plugin architecture for stack implementations
Next concern for the long term maintenance is the management of the objects. This can be done with an abstract factory implementation as shown below.
package clean.project.ds.stack.factory;
public interface StackFactory<ST, T> {
public ST getStack(final int size);
}
package clean.project.ds.stack.factory;
import clean.project.ds.stack.contract.LimitedStack;
import clean.project.ds.stack.impl.LimitedStackImpl;
public class LimitedStackFactory<T> implements StackFactory<LimitedStack<T>, T> {
public LimitedStack<T> getStack(int size) {
return new LimitedStackImpl<T>(size);
}
}
package clean.project.ds.stack.factory;
import clean.project.ds.stack.contract.MonitoredLimitedStack;
import clean.project.ds.stack.impl.MonitoredLimitedStackImpl;
public class MonitoredLimitedStackFactory<T> implements StackFactory<MonitoredLimitedStack<T>, T> {
public MonitoredLimitedStack<T> getStack(int size) {
return new MonitoredLimitedStackImpl<T>(size);
}
}
package clean.project.ds.stack.factory;
public class StackFactoryBuilder<T> {
public LimitedStackFactory<T> buildLimitedStackFactory() {
return new LimitedStackFactory<T>();
}
public MonitoredLimitedStackFactory<T> buildMonitoredLimitedStackFactory() {
return new MonitoredLimitedStackFactory<T>();
}
}
UML Diagram for the factory package
Also note the use of generics to define factories & builders. With this approach we get two benefits - one we have control over object creation, and second without any extra code we can have stacks for any types of elements.
This is how the usage will look like.
Parantheses Syntax Checker
package clean.project.ds.stack.application;
import clean.project.ds.stack.contract.LimitedStack;
import clean.project.ds.stack.factory.StackFactoryBuilder;
public class ParenthesesSyntaxChecker {
private static StackFactoryBuilder<Character> characterStackFactoryBuilder = new StackFactoryBuilder<Character>();
private boolean checkParenthesisSyntax(final String input) throws Exception {
final LimitedStack<Character> characterLimitedStack = characterStackFactoryBuilder.buildLimitedStackFactory().getStack(100);
char [] inputAsCharArray = input.toCharArray();
boolean isValid = true;
for (char currentChar : inputAsCharArray) {
if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
characterLimitedStack.push(currentChar);
}
if (currentChar == ')' || currentChar == ']' || currentChar == '}') {
if (characterLimitedStack.isEmpty()) {
isValid = false;
} else {
Character stackTop = characterLimitedStack.pop();
if (getMatchingOpener(currentChar) != stackTop) {
isValid = false;
}
}
}
}
if (!characterLimitedStack.isEmpty()) {
isValid = false;
}
return isValid;
}
private char getMatchingOpener(final char closer) {
if (closer == ')') {
return '(';
} else if (closer == ']') {
return '[';
} else if (closer == '}') {
return '{';
}
return ' ';
}
public static void main(String[] args) {
final String firstExample = "[(A + B])";
final String secondExample = "(A + B) - {C + D} - [F + G]";
final String thirdExample = "((H) * {([J + K])})";
final String [] examples = {firstExample, secondExample, thirdExample};
final ParenthesesSyntaxChecker parenthesesSyntaxChecker = new ParenthesesSyntaxChecker();
for (String example: examples) {
try {
System.out.println(String.format("The syntax for example \"%s\" is valid? : %s", example, parenthesesSyntaxChecker.checkParenthesisSyntax(example)));
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
To summarise, below is the UML diagram of the entire code
Infix to Postfix Converter
package clean.project.ds.stack.application;
import clean.project.ds.stack.contract.MonitoredLimitedStack;
import clean.project.ds.stack.factory.StackFactoryBuilder;
public class InfixToPostfixConverter {
private static StackFactoryBuilder<Character> characterStackFactoryBuilder = new StackFactoryBuilder<Character>();
private void convertInfixToPostfix(final String input) throws Exception {
MonitoredLimitedStack<Character> characterMonitoredLimitedStack = characterStackFactoryBuilder.buildMonitoredLimitedStackFactory().getStack(100);
System.out.println("Input: " + input);
final StringBuffer postfixStringBuffer = new StringBuffer();
char [] inputAsCharArray = input.toCharArray();
for (char currentChar : inputAsCharArray) {
if (!OperatorPrecedence.isOperator(currentChar)) {
postfixStringBuffer.append(currentChar);
} else {
while (!characterMonitoredLimitedStack.isEmpty()
&& OperatorPrecedence.isLeftOperatorOfHigherPrecedence(characterMonitoredLimitedStack.peek(), currentChar)) {
char topSymbol = characterMonitoredLimitedStack.pop();
postfixStringBuffer.append(topSymbol);
}
characterMonitoredLimitedStack.push(currentChar);
}
}
while (!characterMonitoredLimitedStack.isEmpty()) {
char topSymbol = characterMonitoredLimitedStack.pop();
postfixStringBuffer.append(topSymbol);
}
System.out.println("Output: " + postfixStringBuffer.toString());
}
public static void main(String[] args) {
final InfixToPostfixConverter infixToPostfixConverter = new InfixToPostfixConverter();
try {
infixToPostfixConverter.convertInfixToPostfix("A*B+C*D");
} catch (Exception e) {
e.printStackTrace();
}
}
}
enum OperatorPrecedence {
DIVISION(4, '/'), MULTIPLICATION(3, '*'), ADDITION(2, '+'), SUBTRACTION(1, '-');
private int precedence;
private char symbol;
private static final OperatorPrecedence [] VALUES = values();
OperatorPrecedence(final int precedence, final char symbol) {
this.precedence = precedence;
this.symbol = symbol;
}
public static boolean isOperator(final char symbol) {
for (OperatorPrecedence operatorPrecedence : VALUES) {
if (operatorPrecedence.symbol == symbol) {
return true;
}
}
return false;
}
public static boolean isLeftOperatorOfHigherPrecedence(final char left, final char right) throws Exception{
OperatorPrecedence leftOperator = findEnumForOperator(left);
OperatorPrecedence rightOperator = findEnumForOperator(right);
boolean isLeftHigher = false;
if (leftOperator.precedence > rightOperator.precedence) {
isLeftHigher = true;
}
return isLeftHigher;
}
private static OperatorPrecedence findEnumForOperator(final char operator) throws Exception {
for (OperatorPrecedence operatorPrecedence : VALUES) {
if (operatorPrecedence.symbol == operator) {
return operatorPrecedence;
}
}
throw new Exception("Operator enum not found for operator " + operator);
}
}
You can find the full code at https://github.com/priyeshkpandey/clean-data-structures
No comments:
Post a Comment