patternjavaMinor
Expression tree creation from postfix expression
Viewed 0 times
expressionpostfixfromcreationtree
Problem
Given a postfix expression, construct an expression tree. Looking code code review, optimizations and best practices.
```
public class ExpressionTree {
private final String postfix;
private TreeNode root;
/**
* Takes in a valid postfix expression and later its used to construct the expression tree.
* The posfix expression, if invalid, leads to invalid results
*
* @param postfix the postfix expression.
*/
public ExpressionTree(String postfix) {
if (postfix == null) { throw new NullPointerException("The posfix should not be null"); }
if (postfix.length() == 0) { throw new IllegalArgumentException("The postfix should not be empty"); }
this.postfix = postfix;
}
private static class TreeNode {
TreeNode left;
char ch;
TreeNode right;
TreeNode(TreeNode left, char ch, TreeNode right) {
this.left = left;
this.ch = ch;
this.right = right;
}
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
/**
* Constructs an expression tree, using the postfix expression
*/
public void createExpressionTree() {
final Stack nodes = new Stack();
for (int i = 0; i < postfix.length(); i++) {
char ch = postfix.charAt(i);
if (isOperator(ch)) {
TreeNode rightNode = nodes.pop();
TreeNode leftNode = nodes.pop();
nodes.push(new TreeNode(leftNode, ch, rightNode));
} else {
nodes.add(new TreeNode(null, ch, null));
}
}
root = nodes.pop();
}
/**
* Returns the prefix notation
*
* @return the prefix notation
*/
public String prefix() {
if (root == null) {
throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
}
final Stri
```
public class ExpressionTree {
private final String postfix;
private TreeNode root;
/**
* Takes in a valid postfix expression and later its used to construct the expression tree.
* The posfix expression, if invalid, leads to invalid results
*
* @param postfix the postfix expression.
*/
public ExpressionTree(String postfix) {
if (postfix == null) { throw new NullPointerException("The posfix should not be null"); }
if (postfix.length() == 0) { throw new IllegalArgumentException("The postfix should not be empty"); }
this.postfix = postfix;
}
private static class TreeNode {
TreeNode left;
char ch;
TreeNode right;
TreeNode(TreeNode left, char ch, TreeNode right) {
this.left = left;
this.ch = ch;
this.right = right;
}
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
/**
* Constructs an expression tree, using the postfix expression
*/
public void createExpressionTree() {
final Stack nodes = new Stack();
for (int i = 0; i < postfix.length(); i++) {
char ch = postfix.charAt(i);
if (isOperator(ch)) {
TreeNode rightNode = nodes.pop();
TreeNode leftNode = nodes.pop();
nodes.push(new TreeNode(leftNode, ch, rightNode));
} else {
nodes.add(new TreeNode(null, ch, null));
}
}
root = nodes.pop();
}
/**
* Returns the prefix notation
*
* @return the prefix notation
*/
public String prefix() {
if (root == null) {
throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
}
final Stri
Solution
Make your structs immutable
Choose your validations
Don't throw
Choose your comments
Most of your comments do not add much to the methods, and are therefore redundant. Let the names of the method and variables do the work for you. If you feel the name
Being nice is better than being strict
Unless there is some requirement restriction, I don't think you need to throw an exception if
Since there is no meaning for calling
Use the power of String
Use
TreeNode is a helper structure, with public members, which is fine, but you better make them final, so you know they won't be changed after the object is created.Choose your validations
Don't throw
NullPointerException on your own. It may confuse a future debugger. Either throw an IllegalArgumentException or let the runtime throw the NullPointerException for you.Choose your comments
Most of your comments do not add much to the methods, and are therefore redundant. Let the names of the method and variables do the work for you. If you feel the name
prefix is not clear enough on its own, it is better to rename it (maybe to toPrefixNotation()) and then you can safely remove your comments.Being nice is better than being strict
Unless there is some requirement restriction, I don't think you need to throw an exception if
root is null - why not simply call createExpressionTree() instead of telling the developer he should?Since there is no meaning for calling
createExpressionTree() twice (postfix is final...), you might as well hide it altogether, and call it when needed.Use the power of String
Use
String#indexOf to make isOperator more succinct:private boolean isOperator(char c) {
return "+-*/".indexOf(c) != -1
}Code Snippets
private boolean isOperator(char c) {
return "+-*/".indexOf(c) != -1
}Context
StackExchange Code Review Q#46894, answer score: 8
Revisions (0)
No revisions yet.