Evaluating Expressions

When we evaluate an arithmetic expression like:

(3 + 7 * 2) * (6 + 15);

we need to follow specific rules and learn to think systematically about the procedure we are following to do some operation, like evaluating arithmetic expressions.

The ability to know and follow the procedure the computer will use to do a particular operation is an important part of programming. We are not trying to exactly mimic the computer, rather form a model of computation in our heads that then can be used to understand the interpretation of the program.

Learn to think like the interpreter.

---

The Evaluation Process

Every time you evaluate a combination like a + b, the evaluator does two things:

1. First, it evaluates each operand. Both a and b.
2. Then it applies the operator (like +) to the results.

This means the process of evaluating an expression includes evaluating its parts, which are often combinations themselves. So the rule is recursive by nature.

---

Expression Trees

We can imagine this process as a tree: each node is a combination, and each child is either a number or another combination. Evaluation proceeds from the leaves (numbers) upward to the root, combining results as it goes.

For (3 + 7 * 2) * (6 + 15):

graph TD
    root["357"]
    rootL["17"]
    rootOp["*"]
    rootR["21"]

    left3["3"]
    leftOp["+"]
    leftR["14"]

    mul7["7"]
    mulOp["*"]
    mul2["2"]

    right6["6"]
    rightOp["+"]
    right15["15"]

    root --> rootL
    root --> rootOp
    root --> rootR

    rootL --> left3
    rootL --> leftOp
    rootL --> leftR

    leftR --> mul7
    leftR --> mulOp
    leftR --> mul2

    rootR --> right6
    rootR --> rightOp
    rootR --> right15

    classDef leaf fill:transparent,stroke:#0061a4,color:#0061a4
    classDef intermediate fill:transparent,stroke:#6e7685,color:#4a5060
    classDef op fill:transparent,stroke:#6e7685,color:#4a5060

    class left3,mul7,mul2,right6,right15 leaf
    class root,rootL,rootR,leftR intermediate
    class rootOp,leftOp,mulOp,rightOp op

The leaves (numbers, in blue) are evaluated first. Then the results accumulate upward; each operator combines its children’s values until we reach the root.

This is called tree accumulation, a general technique for dealing with hierarchical structures.

---

What You’ll Do

In this problem, you’ll write rules for evaluating simple arithmetic expressions built from numbers and operators.

Your job is to fill in the pattern rules that tell the evaluator what to do when it sees:

• A number
• A combination like [2, "+", 3]
• A nested expression like [3, "+", [7, "*", 2]]

---

How the Evaluator Works

You’ll work with a function like this:

function evaluate(expr) {
  return match(expr, {
    "n": (n) => ...,
    "l + r": (l, r) => ...
  });
}

The evaluator already knows how to match the patterns. You just write what should happen when it sees a number or a combination.

Let’s begin.