Evaluating Expressions with Variables
A symbol table stores variable names as keys and their double values as the associated values, so an expression evaluator can retrieve a variable's value when it appears in an expression.
A Name the Evaluator Cannot Yet Resolve
Imagine a program that reads arithmetic expressions typed by a user. The expressions may contain names such as x or rate, along with numbers, operators, and parentheses. When the program meets the name rate, it has to find a number to substitute for it. A name in an expression stands for a value, and the program can only compute the expression once it knows that value.
Many learners assume that asking a collection for a name always produces a value, so the next step is simply to use whatever comes back. That assumption is the misconception this article corrects. The program must handle the case where a name has never been given a value, and the way a map reports that case is easy to overlook.
What do you think happens?
Suppose a symbol table has been created but no value has ever been stored under the name y. The program then asks the table for the value of y. What does the program receive back?
Reveal answer
null
The source states that get() returns null when no value has ever been assigned to a variable. Nothing in that result announces an error by itself, so the program has to test for it.
What a Symbol Table Stores
A symbol table stores variable names as keys and their double values as the associated values, so an expression evaluator can retrieve a variable's value when it appears in an expression.
The two halves of each entry play different roles. The key is the variable name, which is how the program identifies what it is looking for. The value is the number currently associated with that name, and in this program every value is of type double. Because a map associates keys with values, it is a natural fit for this job. The table is where the user's assignments live, so the evaluator has a single place to look whenever a name appears in an expression.
Tracing the Table as Entries Arrive
Consider a table that has received two assignments: the user has set x to 4.0 and rate to 0.5. The diagram below shows the table's state at that moment. Each name is a key, and the number stored under it is the value. A lookup of x returns the value attached to the key x, which is 4.0.
Declaring the Table with Map and HashMap
The source states that the symbol table is an object of type Map<String,Double>. The first type parameter is the key type, which is String because keys are variable names. The second is the value type, which is Double because values are numbers of type double. Primitive types such as double cannot be used as type parameters, which is why the wrapper class Double is used instead.
The table is held in a variable whose declared type is Map<String,Double>, and it is created at the start of the program with an empty-diamond constructor call to HashMap. The diamond tells Java to infer the type arguments from the declaration. The declared type names the interface, which describes what the table can do, while the constructor call names the implementation that actually stores the entries.
- Map<String,Double> is the interface type: key type String, value type Double
- new
HashMap<>() is the implementation and the empty-diamond constructor call - put takes the variable name and its value as its two arguments
- Each assignment the user makes becomes one call to put
Choosing HashMap Over TreeMap
The source names two possible implementations for the symbol table. A TreeMap could also be used. The program uses a HashMap, and the reason is practical: the program never needs to access the variables in alphabetical order, so there is no reason to keep the keys in sorted order. The choice depends on what the program needs to do with the stored data, not on which implementation sounds more powerful.
| Aspect | HashMap | TreeMap |
|---|---|---|
| Role in this program | Stores name-to-value entries for lookup | Could also store the same entries |
| Key ordering | Keys are not kept in sorted order | Keys are kept in sorted order |
| Needed for this evaluator? | Yes, since only lookups by name are required | Not required, because alphabetical order is never used |
Both are maps that associate names with values. The decision turns on whether sorted key order is a requirement of the program.
Choose the map implementation by asking what operations the program performs on the stored data. If the program only needs to look up values by name, sorted key order adds nothing that the evaluator uses.
What get() Returns for an Unassigned Name
The program below stores two values and then asks for both a stored name and a name that was never stored. The second request is the case the source warns about. The program is original to this article and is built on the same put and get calls shown earlier.
4.0
nullget("x")finds the key x and returns its stored valueget("y")finds no entry for y and returns null
Reading the output carefully is the important part. The first line is a stored value. The second line is null, and nothing in that output announces an error. The map simply reports that no value exists under the name y. A program that does not look at that result will carry the null forward silently.
Following a Lookup Through the Evaluator
When the evaluator meets a variable inside an expression, it calls get() with that variable's name. The returned value either flows on to the calculation or, if it is null, is routed to the error branch. The null test has to come immediately after the lookup, before the value is used anywhere else.
Evaluating x + rate with a null check
The table holds x = 4.0 and rate = 0.5. Evaluate the expression x + rate, checking each lookup for null before using it.
- 1Look up x
get("x")returns 4.0, which is not null, so the value can be used. - 2Look up rate
get("rate")returns 0.5, which is not null, so the value can be used. - 3Compute the sum
With both values confirmed, the evaluator computes 4.0 + 0.5.
4.5
Error: undefined variable y- The null test comes directly after the lookup
- A null result is reported as an error instead of being used as a number
Mistakes When Handling Lookups
Common mistake Assuming get() always returns a number
What it looks likedouble total = symbols.get("y") + 1;Why it failsIf y was never assigned,
get("y")returns null, and unboxing null in arithmetic fails.Do this insteadStore the result in a Double, test it against null, and only then use it in arithmetic.
Common mistake Testing for null after the value has already been used
Why it failsA null that is used first has already caused the problem the null test was meant to prevent.
Do this insteadPlace the null check immediately after the lookup, before the value is used anywhere else.
Common mistake Treating null as a zero value
Why it failsThe source says null signals that the user is using an undefined variable. It is not the same as the number 0.0.
Do this insteadReport an error for null rather than substituting a default number.
Common mistake Choosing TreeMap because it sounds more powerful
Why it failsThe program never accesses variables in alphabetical order, so sorted key order gives it nothing it needs.
Do this insteadPick the implementation based on the operations the program actually performs, which here is name-based lookup.
Checking Your Understanding of Lookups
A user types the expression rate * 10 after only assigning x. Trace what the evaluator does when it reaches rate. What does get("rate") return, and what must the program do before multiplying?
Hints
- Ask whether any value was ever put under the key rate.
- Think about where the null test has to appear relative to the multiplication.
Key Takeaways for Symbol Tables
- 1A symbol table maps variable names to their double values, so the evaluator can retrieve a value whenever a name appears in an expression.
- 2The table is declared as Map<String,Double> and backed by a
HashMap, with put storing each assignment. - 3
get()returns null for a name that has never been assigned, which signals an undefined variable and must be tested before the value is used. - 4
HashMapis sufficient here because the program never needs variables in alphabetical order.
At a glance
- A symbol table stores variable names as keys and double values as values, letting an evaluator look up a name found in an expression.
- The table is declared as Map<String,Double> and backed by a
HashMap, and each assignment is stored with put. get()returns null for a variable that was never assigned, signalling an undefined variable that must be caught by a null check right after the lookup.HashMapsuits this evaluator because only name-based lookup is needed, so sorted key order fromTreeMapadds nothing.