Postfix$++$

Postfix$++$ is a stack$-$based computer language directed at the evaluation of arithmetic

expressions. You will implement a Postfix$++$ interpreter that can evaluate Postfix$++$ code line$-$by$-$

line, as entered, for example, on a mobile device.

Postfix arithmetic

Operators, in postfix arithmetical expressions, follow operands. For example, $34+$ means $3+4.$

The postfix expression $345+{?}^{**}$ is evaluated as follows:

$345+*$

${39}^{**}($replace $45+$ with the result of adding $4$ to $5)$

$27($replace $39*$ with $27)$

Postfix expressions are conveniently evaluated using a stack. An expression consisting of

operands and operators $($collectively$,$ 'tokens'$),$ is read from left to right. Successive operands are

pushed on a stack until an operator arrives. The appropriate number of operands are then popped

from the stack, combined with the operator, and the result is pushed back on the stack. The result

of a calculation is always to be found at the top of the stack. A stack is notated $[$a b c$...]$ in the

following example; the stack top is the leftmost token.

Postfix with variables

The $\text{'}++\text{'}$ refers to an enhanced form of postfix: a postfix with variables. Expressions can contain

variable names; the value of the variable is used for the calculation. The assignment operator $\text{'}="$

assigns a value to a variable. For example

$A3=$

will set the value of $A$ to $3.$ It is equivalent to the infix assignment statement $A=3$ that is to be

found in many computer languages.

An interactive session might proceed as follows

$>A2=$

$>B3=$

$>AB*$

$[6]$

Symbol Table

A symbol table data structure associates keys with values. For example,

A generic symbol table should support two operations, INSERT and SEARCH. There may also be

a DELETE operation. No assumptions are made on the type and format of keys and values.

You will need a symbol table in your Postfix$++$ interpreter. The table will map variable name $($key$)$

to value.

The target hardware

A Postfix$++$ interpreter might run on a small device with very limited memory. This means that the

variable namespace is small, for example, $\text{'}A\text{'}-\text{'}Z\text{'}.$