### Stack applications

Q$1)$The first two exercises ask you to use the stack data structure to develop two distinct stack$-$driven applications.

The completed stack implementation can be found in $`$stack$.$py$`.$ It is merely included for reference $---*$you should not modify this implementation$*$ to complete these exercises.

### $1.$ Paired delimiter matching $(10$ points$)$

For this exercise you will implement the code to accept a dictionary which maps opening to closing delimiters $($with the caveat that all delimiters are one$-$character strings$).$

E$.$g$.,$ the following calls should return $`$True$`$:

check$\_$delimiters$(\text{'}((()()))\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'}\})$

check$\_$delimiters$(\text{'}[<>()[()()]]\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}<\text{'}$:$\text{'}>\text{'},\text{'}[\text{'}$:$\text{'}]\text{'}\})$

check$\_$delimiters$(\text{'}("$bob$","$ma$","$ry$",("$tom$"))\text{'},\{\text{'}(\text{'}$: $\text{'})\text{'},\text{'}"\text{'}$: $\text{'}"\text{'}\})$

E$.$g$.,$ the following calls should return $`$False$`$

check$\_$delimiters$(\text{'}([$a b$)]\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}[\text{'}$:$\text{'}]\text{'}\})$

check$\_$delimiters$(\text{'}("$hi $"(")$ there"$)\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}"\text{'}$:$\text{'}"\text{'}\})$

Note that there may be delimiters used in the string that are not in the dictionary. These should be ignored.

It is also possible that a pair of opening and closing delimiters use the same character $($e$.$g$.,`\text{'}"\text{'}`$ and $`\text{'}"\text{'}`),$ in which case $*$they cannot be nested$*$ i$.$e$.,$ if you encounter a delimiter of this type and it is already on the stack, you should pop it off the stack rather than push another one on$.$

E$.$g$.,$ while the following call should return $`$False$`($because the brackets, which nest, are not correctly matched$)$:

check$\_$delimiters$(\text{'}([[)(]])\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}[\text{'}$:$\text{'}]\text{'}\})$

the following calls should also return $`$False$`($because the double quotes do not nest$)$:

check$\_$delimiters$(\text{'}("("""))\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}"\text{'}$:$\text{'}"\text{'}\})$

check$\_$delimiters$(\text{'}(")(")(")(")\text{'},\{\text{'}(\text{'}$:$\text{'})\text{'},\text{'}"\text{'}$:$\text{'}"\text{'}\})$

Your implementation will go into the $`$check$\_$delimiters$`$ function in $`$stack$\_$apps.py$`.$

Q$2).$ Another function we examined in class was one that used a stack to evaluate a postfix arithmetic expression. Because most of us are more accustomed to infix$-$form arithmetic expressions $($e$.$g$.,`\text{'}2*(3+4)\text{'}`),$ however, the function seems to be of limited use. The good news: we can use a stack to convert an infix expression to postfix form!

To do so$,$ we will use the following algorithm:

$1.$ Start with an empty list $L$ and an empty stack $S$$.$ At the end of the algorithm, $L$ will contain the correctly ordered tokens of the postfix expression.

$2.$ For each white$-$space separated token $T$ in the infix expression, carry out the first of the following rules that applies:

$-$ If $T$ is a number, simply append it to $L$$.$

$-$ If $S$ is empty or the top of $S$ is a left parenthesis, push $T$ onto $S$$.$

$-$ If $T$ is a left parenthesis, push it onto $S$$.$

$-$ If $T$ is a right parenthesis, keep popping values from $S$ and appending them to $L$ until a left parenthesis is popped from $S$$.$ Note that the parentheses themselves are not appended to $L$$.$

$-$ If $T$ has higher precedence than the top of $S$ $($or if the top of $S$ is a left parenthesis$),$ push it onto $S$$.$

$-$ If $T$ has equal precedence with the top of $S$$,$ pop $S$ and append the popped value to $L$$,$ then push $T$ onto $S$$.$

$-$ If $T$ has lower precedence than the top of $S$$,$ pop $S$ and append the popped value to $L$$.$ Then repeat these last three tests against the new top of $S$$.$

$3.$ After arriving at the end of the expression, pop and append all operators on $S$ to $L$$.$

For your implementation, you will only need to handle the operators $`+`,`-`,`*`,$ and $`/`,$ where the first two have lower precedence than the second two. Assume that all expressions are well$-$formed $($i$.$e$.,$ valid$).$

Your implementation will go into the $`$infix$\_$to$\_$postfix$`$ function in $`$stack$\_$apps.py$`.$

stack$\_$apps.py

from stack import Stack

def check$\_$delimiters$($expr: str$,$ delims: dict$[$str$,$str$])->$ bool:

pass

def infix$\_$to$\_$postfix$($expr: str$)->$ str:

pass