Stack Machine Code for Expressions

A BinOpNode stores an operator and two child expression nodes, and its value is computed by applying the operator to the values of those children.

Programming

From Text to Structure

Read the text -3 + 4 as a person would and you see a sum: a negative three added to four. A program does not start with that understanding. To the program, the expression is just a line of characters. Before it can compute anything, something has to turn those characters into a structure it can work with. This article follows that transformation step by step, using the classes that hold the structure and the function that builds it.

The code that does this comes from a recursive descent parser. As the parser reads input, it creates node objects that the source defines for each kind of piece in the expression. The goal of this article is to be able to say, at any point in the construction, what the parser has built so far and what it is about to build next.

What do you think happens?

Before reading on: when the parser reads the text -3 + 4, what is the root of the tree it returns, and what kind of node is that root?

A UnaryMinusNode, because the expression starts with a minus sign
A BinOpNode whose operator is +, because the + is the last operator the parser combines

Reveal answer

Answer:

A BinOpNode whose operator is +

The leading minus wraps only the first term, so it becomes the left child of a BinOpNode. The + operator is combined with the wrapped term and the term 4 to form the root.

Reading -3 + 4 Step by Step

The expressionTree() function reads an expression from the current line of input and returns a tree representing it. The return value is a pointer to the root of the tree. The function reads the first term, then loops over the remaining operators, wrapping the tree built so far together with each new term. Follow the trace below one stage at a time. Each stage names what the parser has built after that step.

After each stage of expressionTree(), what has the parser built so far, and what does it build next?

Read the stages as a sequence of states. At stage 3, the parser already holds a tree whose only node is a UnaryMinusNode, and no BinOpNode exists yet. At stage 5, a new BinOpNode is created that takes the tree built so far as its left child. The root is always the node most recently assigned to exp, so the node created at stage 5 is what the function returns.

What a BinOpNode Holds

A BinOpNode stores an operator and two child expression nodes, and its value is computed by applying the operator to the values of those children. The operator is held in a field named op. In the example above, the binary minus between two terms produces a BinOpNode with op set to '-', and the plus in -3 + 4 produces one with op set to '+'.

The important design choice is that a BinOpNode does not store numbers in its own fields. It stores references to its children, and those children can themselves be BinOpNodes. Because of this, a node's value is found by asking its children for their values. The source writes the value computation as a call to left.value() and right.value(), so evaluation of the whole tree happens by recursion from the root down to the leaves.

java

left.value()
right.value()

left.value()
right.value()

Notes on the code

The BinOpNode asks its left child for a value.
The BinOpNode asks its right child for a value.
Each child may itself be a BinOpNode, so the same request repeats at lower levels of the tree.

When the root is evaluated, its two children are evaluated first, and their results combine into the final value of 1.

Work through the evaluation from the bottom up. The leaf 3 has the value 3. The UnaryMinusNode applies negation to its child and produces -3. The leaf 4 has the value 4. The root's operator is +, so it combines the value of its left child and the value of its right child, giving -3 + 4, which is 1. Notice that the root did not need to know anything about the numbers directly; it only asked its children and combined what they returned.

Leading Minus Versus Binary Minus

A leading minus sign is handled differently from a minus sign between two terms. Between terms, a minus is a binary operator and produces a BinOpNode with op set to '-'. A minus at the very start of the expression is consumed before the first term is read, and it produces a UnaryMinusNode. The source defines a UnaryMinusNode as applying a unary minus operation to its child node, and it is created when a leading minus sign is encountered during parsing.

The UnaryMinusNode wraps only the result of the first termTree() call, not the whole expression. The code does this with exp = new UnaryMinusNode(exp), placed before the loop that handles the remaining operators. Any operators that follow are then combined with this wrapped tree by BinOpNodes. The wrapped first term is therefore the left child of the first BinOpNode, not the root of everything.

java

exp = new UnaryMinusNode(exp)

exp = new UnaryMinusNode(exp)

Notes on the code

This line runs once, after the first term has been read and before the operator loop starts.
It replaces exp with a node whose only child is the previous exp, which is the first term's tree.
Operators read later in the loop do not pass through this line.

Before the loop runs, the tree is only the wrapped first term. After the + operator and the term 4 are read, a new BinOpNode becomes the root and takes the wrapped term as its left child.

The two node kinds differ in how many children they hold. A UnaryMinusNode has one child. A BinOpNode has two. That difference is visible in the diagram above: the wrapped term has one child, and the new root has two.

Tracing a Build That Goes Wrong

Suppose the parser is expected to evaluate -3 + 4 to 1, but a different result appears. The question is where in the construction the value first diverges. The method is to check each stage in order, starting with the leading minus and the first term, and to stop at the first stage that disagrees with what you expect. The earlier stages are the foundation for the later ones, so a wrong early stage can make every later result look wrong too.

Worked example

Finding the first divergence in -3 + 4

The parser should build a tree for -3 + 4 that evaluates to 1, but the final result is wrong. Use the staged check to find the first stage that disagrees with the expected structure.

1
Check the leading minus
Confirm that a UnaryMinusNode was created for the leading minus and that it was not created as a binary '-' operator. If a BinOpNode with op '-' appears at the start, the divergence is already here.
2
Check the first term
Confirm that the UnaryMinusNode's child is the term 3. If the wrapped child is some other value, the error is in reading the first term.
3
Check where the wrap happens
Confirm that the UnaryMinusNode wraps only the first term's tree, before the operator loop. If the negation was applied after the + node was built, it would apply to the whole expression, which is a different tree.
4
Check the binary node
Confirm that the BinOpNode has op '+', its left child is the UnaryMinusNode, and its right child is the term 4. If the right child is wrong, the divergence is at the step that read the second term.
5
Check the returned root
Confirm that the returned root is the most recently created node, which is the BinOpNode. If an earlier node is returned, the function is returning the wrong object.

Result

The first stage that disagrees with the expected structure is the place to fix. Earlier stages that agree can be ruled out, so you only need to examine the stage where the first mismatch appears.

Mistakes Beginners Make When Tracing

Common mistake
Treating the leading minus as a binary operator
What it looks like
Reading -3 + 4 as if it had two operands on the left of the minus.
Why it fails
A minus at the very start of the expression is consumed before the first term is read and produces a UnaryMinusNode. A binary minus only appears between two terms.
Do this instead
Look for a UnaryMinusNode when the expression begins with a minus, and for a BinOpNode with op '-' only when a minus sits between two terms.
Common mistake
Assuming the leading minus negates the whole expression
What it looks like
Believing that -3 + 4 means the negation applies to 3 + 4, which would give -7.
Why it fails
The UnaryMinusNode wraps only the result of the first termTree() call. The later + is combined with the wrapped term by a BinOpNode.
Do this instead
Draw the wrapped first term as the left child of the BinOpNode, so the negation stops at the 3.
Common mistake
Expecting a BinOpNode to hold numbers directly
Why it fails
A BinOpNode stores references to its children, and those children can be other BinOpNodes or other node kinds.
Do this instead
When evaluating, ask each child for its value and combine the results with op. Do not look for the number in the BinOpNode's own fields.
Common mistake
Returning the first node created as the root
Why it fails
The root of the returned tree is the last node assigned to exp, which is the most recently created node. Earlier nodes become children as the tree grows.
Do this instead
Identify the root as the final assignment to exp, then check the tree downward from that node.

Practice Tracing a Build

MEDIUM

Using the stages in this article, trace the construction for -3 + 4. For each stage, write down the node the parser has just created and the node it will create next. Then state the stage where a result would first differ if the leading minus were mistakenly treated as a binary operator.

Hints

Start with the leading minus. Ask whether it is consumed before the first term is read.
A UnaryMinusNode has one child. Count the children of each node you write down.
The first stage that differs from the correct build is where the unexpected result begins.

Your attempt (not saved)

Key Points to Carry Forward

Key Takeaways

A BinOpNode stores an operator and two child expression nodes, and its value is computed by asking its children for their values and combining them with the operator.
expressionTree() reads the first term, wraps it in a UnaryMinusNode only if a leading minus was read, and then creates a new BinOpNode for each remaining + or - operator.
A leading minus produces a UnaryMinusNode that wraps only the first term, while a minus between two terms produces a BinOpNode with op '-'.
The root of the returned tree is the last node assigned to exp, so tracing a build means checking stages in order and stopping at the first stage that disagrees with the expected structure.