Java: ParseTree { Function function; //could be an integer, variable, or arithme
ID: 3706455 • Letter: J
Question
Java: ParseTree {
Function function; //could be an integer, variable, or arithmetic operation
ParseTree left;
ParseTree right;
}
ParseTree parse(Token a[], int left, int right) {
If left == right //a[left] must either be a variable or integer literal
Return the parse tree whose single node is a[left]
Let i be the first array index of the operation of lowest precedence that is not enclosed by parentheses
If i does not exist
//Tokens a[left] and a[right] are left and right parentheses
Return parse(a, left+1, right-1)
Return the parse tree whose root is a[i], whose left subtree is parse(a, left, i-1) and whose right subtree is parse(a, i+1, right)
The user inputs an arithmetic expression (according to the above guidelines), and the program prints the parse tree according to the recursive format.
root
left
right
For example, if the input is (3 + 4) ? x, then the parse tree should appear as
*
+
3
4
x
Explanation / Answer
public class ParseTree {
private String s;
private ParseTree left, right;
// creat the parse tree from standard input
public ParseTree() {
s = StdIn.readString();
if (s.equals("+") || s.equals("*")) {
left = new ParseTree();
right = new ParseTree();
}
}
// evaluate the parse tree
public int eval() {
if (s.equals("+")) return left.eval() + right.eval();
else if (s.equals("*")) return left.eval() * right.eval();
else return Integer.parseInt(s);
}
// preorder traversal
public String toString() {
if (s.equals("+") || s.equals("*"))
return s + " " + left + " " + right;
else
return s;
}
// test out the parse tree
public static void main(String[] args) {
ParseTree tree = new ParseTree();
System.out.println(tree);
System.out.println(tree.eval());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.