public ExpressionTree280( String expr ) throws InvalidState280Exception { // TOD
ID: 3559266 • Letter: P
Question
public ExpressionTree280( String expr ) throws InvalidState280Exception {
// TODO Construct an ExpressionTree by reading in a prefix expression
/* Initialization */
// Let the super class initialize the fields.
super();
// Construct a StringTokenizer that uses space as a delimiter.
StringTokenizer tok = new StringTokenizer(expr," ");
// Construct a stack for nodes we construct.
LinkedStack280<String> nodeStack = new LinkedStack280<String>();
LinkedList280<String> preFix = new LinkedList280<String>();
String curToken = tok.nextToken();
/* Push the first token to the stack: */
// Make sure it exists.
// Make sure it's an operator.
// If fine, push it.
if(this.isOperator(curToken)){
if(nodeStack.isEmpty())
nodeStack.insert(curToken);
else
while(nodeStack.itemExists() && this.precedence(nodeStack.item()) >= this.precedence(curToken)) {
preFix.insertLast(nodeStack.item());
nodeStack.deleteItem();
}
nodeStack.insert(curToken);
}
/* Handle the remaining tokens: */
// While not done:
while(tok.hasMoreTokens()){
if(this.isOperand(curToken)){
preFix.insertLast(curToken);
}
else if(this.)
}
/* There should be a token if we're not done. */
// Throw an exception if there isn't.
// If the token is neither an operator or an operand
// Throw an appropriate exception.
// If the token is an operator/internal node:
// Push it to the stack.
// If it's an operand/leaf:
// If it can go on the left side of top of the stack:
// Insert it there.
// If it can't go on the left of the top of the stack:
// Put the leaf in the right of the top of the stack.
/* Then, repeatedly pop nodes from the top of the stack,
* and place them in the right subtree of the new top of the stack.
* If an expression at the top of the stack still needs a left subtree,
* we stop popping.
*/
// Pop the stack.
// While the new top of the stack has a left node already:
// Set the top of the stack's right as the last popped node.
// If we still have things on the stack after looping:
// then what was popped should go in the left of the top of the stack.
// If we popped everything off the stack, though:
// then we're done.
// Set the root of the tree to the last popped item.
/* Finished looping over the input string. */
// If we're done but there are more tokens:
// throw an appropriate exception
}
Explanation / Answer
The prefix expression formed by prefix traversal uses the standard pre-order tree traversal. No parentheses are necessary.
Pseudocode:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.