Implement the following function:

def create$\_$expression$\_$tree$($prefix$\_$exp$\_$str$)$

The function is given a string prefix$\_$exp$\_$str$,$ which contains an arithmetic

expression in a prefix notation.

When called, it creates and returns a LinkedBinaryTree object, that is the

expression tree representing prefix$\_$exp$\_$str$.$

For example, the call: create$\_$expression$\_$tree$(\text{'}*2+-1564\text{'})$

will create and return the following tree:

$3$

$*$

$3$

$23$

$+$

$3$

$-3$

$4$

$3$

$153$

$6$

Note:

Assume that prefix expression will come in the following format:

$1.$ All operators in the expression will be taken from the four basic arithmetic

operations $(+,-,*$ and $/).$

$2.$ All operands will be positive integers.

$3.$ The tokens in the expression will be separated by a space.

Implementation requirements:

$1.$ The nodes containing operators, should have the operator as a string, and

nodes containing numerals, should have the number as an int.

$2.$ The runtime for creating the expression tree should be linear.

$3.$ You are not allowed to use a stack in your implementation.

Hint: There is more than one way to solve this problem. One way is to start by

creating a list with the expression$$s tokens $($by using the split method$),$ and then

calling a helper function:

def create$\_$expression$\_$tree$\_$helper$($prefix$\_$exp, start$\_$pos$)$

This helper function would be recursive, and in order to efficiently pass the

subexpression that the call should consider, besides the list with the entire

expression, it also gets start$\_$pos, which is the index where the subexpression

starts $($we don$$t know how long the subexpression will be$,$ so we can$$t pass the

ending position too$).$

The call to the helper function would return two values $($as a tuple$)$: the first

would be the subtree it created $($that represent the subexpression starting at

start$\_$pos$),$ and the second would be the size of that subtree $($so you can know

where the next subexpression would start...$).$

b$.$ Use the function you implemented in section $($a$),$ to implement the following

function:

def prefix$\_$to$\_$postfix$($prefix$\_$exp$\_$str$)$

The function is given a string prefix$\_$exp$\_$str$,$ which contains an arithmetic

expression in a prefix notation $($in the format described in section $($a$)).$

When called, it returns the string representation of the postfix equivalent of

prefix$\_$exp$\_$str$.$

For example, the call: prefix$\_$to$\_$postfix$(\text{'}*2+-1564\text{'}),$ will

return: $\text{'}21564+*\text{'}$

Implementation requirement: The runtime of this function should be linear.