1. fix tokenize to pass the doctests

2. to_rpn - implement Dijkstra's Shunting-Yard algorithmdescribedin https://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail (Linksto an external site.)Links to an external site., note: the outputqueue is just a string

3. eval_rpn - implement the left-to-right algorithmat https://en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_evaluation_algorithm (Linksto an external site.)Links to an external site.

import reimport stackimport bitreeimport typingdef is_num(s):    """    Returns True if and only if s can be parsed as an integer    :param s: the string to test    :return: True if and only if s can be parsed as an integer    DO NOT CHANGE THIS CODE!    """    try:        int(s)        return True    except ValueError:        return Falsedef to_num(s: str):    """    If s can be parsed as an integer, return the result of the parse,    otherwise, return s without conversion    :param s: the string to try to convert to a number    :return: if s can be parsed as an integer, return the result of the parse,             otherwise, return s without conversion    DO NOT CHANGE THIS CODE!    """    try:        return int(s)    except ValueError:        return sdef tokenize(exp: str) -> typing.List:    """    Breaks a math expression up into a list of its parts, separates the numbers from the operators    NOTE: Numbers strings in exp that are numbers should be returned as numbers,          the code currently does not do this, you must modify it to do so.    :param exp: the math expression to tokenize    :return: a (Python) list of the parts that make up the expression    >>> tokenize('3 + -4 * 5')    [3, '+', -4, '*', 5]    >>> tokenize('(3 + -4) * 5')    ['(', 3, '+', -4, ')', '*', 5]    """    # TODO: modify the code below to meet the spec    tokens = [t.strip() for t in re.split(r'((?:-?d+)|[+-*/()])', exp)]    return [t for t in tokens if t != '']def is_op(s):    """    Returns True iff s is an operator    :param s: the string to test    :return: True iff s is an operator, and False, otherwise    DO NOT CHANGE THIS CODE!    >>> is_op('+')    True    >>> is_op('-')    True    >>> is_op('*')    True    >>> is_op('/')    True    >>> import random    >>> ascii = ord('+')    >>> while chr(ascii) in '+-*/':    ...     ascii = random.randint(0, 255)    >>> is_op(chr(ascii))    False    """    return str(s) in '+-*/'def precedence(op: str):    """    Returns the precedence value of the specified operator    :param op: the operator    :return: the precedence value of the specified operator,             and False, if it is not one of the four    DO NOT CHANGE THIS CODE!    """    precs = {        '+': 2,        '-': 2,        '*': 3,        '/': 3    }    return precs.get(op, False)def to_rpn(expr: str):    """    Convert the given infix math expression to Reverse Polish Notation (postfix)    Refer to https://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail    for the algorithm details    :param expr: an infix math expression    :return: the Reverse Polish Notation version of the infix expression    >>> to_rpn('3 * -4 + 5')    '3 -4 * 5 + '    >>> to_rpn('3 + -4 * 5')    '3 -4 5 * + '    >>> to_rpn('(3 + -4) * 5')    '3 -4 + 5 * '    """    # TODO: replace pass below with your implementation    passdef to_ast(expr: str):    r"""    Converts the given infix expression to an AST    :param expr: a string with an infix math expression    :return: an abstract syntax tree of the expression    DO NOT CHANGE THIS CODE!    Based on    https://softwareengineering.stackexchange.com/a/254075,    and    https://www.klittlepage.com/2013/12/22/twelve-days-2013-shunting-yard-algorithm/    last access 11/20/2017    >>> to_ast('3 + 4 * -5').execute(bitree.VerticalStringAlgo()) # doctest: +NORMALIZE_WHITESPACE    '+|_ 3|  |_ []|  |_ []|_ *   |_ 4   |  |_ []   |  |_ []   |_ -5      |_ []      |_ []'    >>> to_ast('(3 + -4) * 5').execute(bitree.VerticalStringAlgo()) # doctest: +NORMALIZE_WHITESPACE    '*|_ +|  |_ 3|  |  |_ []|  |  |_ []|  |_ -4|     |_ []|     |_ []|_ 5   |_ []   |_ []'    """    def add_node(stack, op):        """        Helper function to pop two operands from operator_stack and        :param stack:        :param op:        :return:        DO NOT CHANGE THIS CODE!        """        right = stack.pop()        left = stack.pop()        stack.push(bitree.DataNode(op, left, right))    operator_stack = stack.LRStack()    operand_stack = stack.LRStack()    toks = [to_num(t) for t in tokenize(expr)]    for tok in toks:        if is_num(tok):            operand_stack.push(bitree.DataNode(tok))        elif is_op(tok):            while (not operator_stack.is_empty()) and precedence(operator_stack.top()) >= precedence(tok):                add_node(operand_stack, operator_stack.pop())            operator_stack.push(tok)        elif tok == '(':            operator_stack.push(tok)        elif tok == ')':            while (not operator_stack.is_empty()) and operator_stack.top() != '(':                add_node(operand_stack, operator_stack.pop())            if operator_stack.is_empty():                print('Unbalanced parentheses')                return None            # else:            operator_stack.pop()    while not operator_stack.is_empty():        add_node(operand_stack, operator_stack.pop())    return operand_stack.pop()def eval_rpn(expr: str):    """    Evaluates the Reverse Polish Notation expression    :param expr: a string containing a Reverse Polish Notation expression    :return: the result of evaluating the RPN expression    Refer to the left-to-right algorithm at    https://en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_evaluation_algorithm    for the algorithm details    >>> eval_rpn('3 -4 * 5 +')    -7    >>> eval_rpn('3 -4 5 * +')    -17    >>> eval_rpn('3 -4 + 5 * ')    -5    """    # TODO: replace pass below with your implementation    passif __name__ == '__main__':    # This is here for your own use    pass