You defeated the Hachimi cat, but as it fled, it hissed one last curse at you:

"You think throwing random items at me is funny? That's it, you are getting cursed! You will never see what the declaration of any classes ever again!"

You arrive at the Lab. You download the code for the partial judge, but something is wrong. The derived class declarations are completely gone, just the base interface class, some factory functions, and a comment:

// You cannot see what's inside. You can only use what's declared here.

You look back at the code, and realize you need to implement the derived classes yourself. The factory functions are your only clue, read what they take as arguments, and you'll know what each class needs to store.

Background

The partial judge evaluates mathematical expressions like add(mul(2,3),4). Every expression is a tree of Term objects. Each node in the tree is one of three kinds:

What to Implement

Numbers

A number term stores a single int.

• Constructor receives one int. Store it.
• isNumber() returns true.
• asInt() returns the stored integer.
• print() prints the integer.
• clone() returns a new independent integer term with the same value.

Variables

A variable term stores a name. The engine will never try to do arithmetic on it.

• Constructor receives one string. Store it.
• asStr() returns the stored name.
• print() prints the name.
• clone() returns a new independent variable term with the same name.

Function Calls

A function call stores a func name and an array of child Term* arguments.

• Constructor receives a string func, a Term** array, and a count n. The array you receive may be deleted right after this call returns, so allocate your own array and copy the pointers in.
• Destructor: the children are yours to manage. Delete each one, then delete the array.
• isFuncCall() returns true.
• asStr() returns the stored func name.
• arity() returns n.
• arg(int i) returns the pointer at position i.
• print() prints func(arg0,arg1,...), calling print() on each child recursively.
• clone(): allocate a new array, clone each child into it, construct a new function call from that, then delete the temporary array before returning.

The evaluate Function

Term* evaluate(const Term* t);

Build and return a fully evaluated copy of t. Do not modify, delete, or store t or any of its children.

• If t is a number or variable, return a clone.
• If t is a function call, recursively evaluate each child to produce a new array of results. Then:
  • If every result is a number, fold them and return a single number. add computes the sum, mul computes the product.
    Note, the evaluated children you produced are heap allocated (malloc or new in the factory functions). If you fold them into a single number, you need to delete those evaluated children before returning, otherwise they will leak.
  • Otherwise return a new function call built from the evaluated children. The new function will take the evaluated children as input, so no need to deallocate them now.

Constraints

1 <= value <= 100, arity <= 10, names contain lowercase letters only with 1 <= len <= 100. Function call funcs are always add or mul.