Recall $**$Cambridge Polish Notation$**(**$CPN$**),$ in which operators and their operands are enclosed in parenthesis.

For example, $`($add $12)`$ is the $**$CPN$**$ equivalent of $`1+2`.$

Expressions in $**$CPN$**$ can be nested, so the following expression would be valid, and would result in $`6`.$

$```$

$($add $1($add $23))$

$```$

Your must create a functioning $**$CPN$**$ calculator which works with the functions listed in the $**$FUNC$\_$TYPE$**$ enum in the provided code through the $**$MIN$\_$FUNC$**$ function $($all functions appearing after $**$MIN$\_$FUNC$**$ in the enum will be implemented in later tasks.

This calculator will serve as the core functionality for $**$CI$-$LISP$**.$

You may want to check out the $[$sample runs$]($#sample$-$runs$)$ below better understand what will be implemented before reading further.

The initial grammar is as follows:

$```$

program ::$=$ s$\_$expr EOL $|$ s$\_$expr EOFT $|$ EOL $|$ EOFT

s$\_$expr ::$=$ f$\_$expr $|$ number $|$ QUIT

f$\_$expr ::$=($ FUNC s$\_$expr$\_$section $)$

s$\_$expr$\_$section ::$=$ s$\_$expr$\_$list $|$

s$\_$expr$\_$list ::$=$ s$\_$expr $|$ s$\_$expr s$\_$expr$\_$list

FUNC ::$=$ neg $|$ abs $|$ add $|$ sub $|$

mult $|$ div $|$ remainder $|$ exp $|$

exp$2|$ pow $|$ log $|$ sqrt $|$

cbrt $|$ hypot $|$ max $|$ min

number ::$=$ INT $|$ DOUBLE

INT ::$=$ optional $+/-,$

then some digits

DOUBLE ::$=$ optional $+/-,$

then some digits,

then a decimal point,

then optionally some more digits

QUIT ::$=$ quit

$```$

The non$-$terminals $**$s$\_$expr$**$ and $**$f$\_$expr$**$ are shorthand:

$***$s$\_$expr$**$ means $*$symbolic$*$ expression

$***$f$\_$expr$**$ means $*$function$*$ expression

## DATA STRUCTURES

Next we'll discuss the structures provided in $[$cilisp$.$h$](../$src$/$cilisp$.$h$).$ For a more intuitive understanding of the structures and their names defined here, note that $**$AST$**$ is short for $*\_\_$A$\_\_$bstract $\_\_$S$\_\_$yntax $\_\_$T$\_\_$ree$*.$ As such, the structures discussed below are intended to house data in an abstract syntax tree.

### NUMBERS

The $**$NUM$\backslash \_$TYPE$**$ enum and $**$AST$\backslash \_$NUMBER$**$ struct define everything necessary to house both numeric data types $($integers and floating point values$)$ in a single struct.

$```$c

typedef enum num$\_$type $\{$

INT$\_$TYPE,

DOUBLE$\_$TYPE

$\}$ NUM$\_$TYPE;

typedef struct $\{$

NUM$\_$TYPE type;

double value;

$\}$ AST$\_$NUMBER;

typedef AST$\_$NUMBER RET$\_$VAL;

$```$

Note that even when an $**$AST$\backslash \_$NUMBER$**\text{'}$s type is $**$INT$\backslash \_$TYPE$**,$ we will be storing it's actual value as a double under the hood. This is to make function evaluation a little less tedious; students wishing to instead use this alternative $**$AST$\backslash \_$NUMBER$**$ are welcome to do so:

$```$c

typedef struct $\{$

NUM$\_$TYPE type;

union $\{$

double floating$\_$point;

long integral;

$\}$ value;

$\}$ AST$\_$NUMBER;

$```$

Each $**$AST$\backslash \_$NUMBER$**$ will house a member of the $**$NUM$\backslash \_$TYPE$**$ enum $($denoting the type of number being stored$)$ alongside a numeric value.

The last line, which gives the $**$AST$\backslash \_$NUMBER$**$ struct a second name $(**$RET$\backslash \_$VAL$**),$ exists exclusively for readability; when we evaluate a part of our syntax tree, the result will always be a number. We will use $**$AST$\backslash \_$NUMBER$**$s to house numbers which are $*$part of$*$ the syntax tree, and $**$RET$\backslash \_$VAL$**$s to house the results of evaulation $(*\_\_$RET$\_\_$urned $\_\_$VAL$\_\_$ues$*).$

### FUNCTIONS

The terms "operator" and "function" will be used interchangeably for our discussion here.

We'll start our discussion of functions with the enum and struct definitions in $[$cilisp$.$h$](../$src$/$cilisp$.$h$).$

$```$c

typedef enum func$\_$type $\{$

NEG$\_$FUNC,

ABS$\_$FUNC,

ADD$\_$FUNC,

$//$ TODO complete the enum

CUSTOM$\_$FUNC

$\}$ FUNC$\_$TYPE;

$```$

This enum will list all functions which will be implemented throughout the course of the project. Clearly, it isn't yet complete, hence the $`$TODO$`.$ You'll add more functions to it as you work through this task, and through future tasks.

When function calls are parsed as $**$f$\_$expr$**$s$,$ the data for said calls will be stored in an $**$AST$\backslash \_$FUNCTION$**$:

$```$c

typedef struct $\{$

FUNC$\_$TYPE func;

struct ast$\_$node $*$opList;

$\}$ AST$\_$FUNCTION;

$```$

This struct stores the operator used in the function call $($a member of the $**$FUNC$\backslash \_$TYPE$**$ enum$)$ and the operands for the function $($a linked list of $**$struct ast$\backslash \_$node$**$s$,$ which we will discuss in the $[$GENERIC NODES$]($#generics$)$ section below$).$

Take note of the $**$resolveFunc$**$ function

$[$cilisp$.$c$](../$src$/$cilisp$.$c$).$ This function takes as input a function's name $($in string form$),$ and outputs the corresponding $**$FUNC$\backslash \_$TYPE$**$ member. It will be used to assign value to $**$FUNC$**$ tokens while lexing.

$**$resolveFunc$**$ works because the array of function names $(**$funcNames$**,$ in $[$cilisp$.$c$](../$src$/$cilisp$.$c$))$ lists all functions in the same order as the $**$FUNC$\backslash \_$TYPE$**$ enum. If either of these is edited, the other must also be edited to match. If they are not kept in sync$,**$resolveFunc$**$ will not work. $**$CUSTOM$\backslash \_$FUNC$**$ should be left as the last element of $**$resolveFunc$**$ for the same reason; user$-$defined functions will be implemented at the end of the project, and we'll know a function