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

Answer rating: 100% (QA)

To fix the tokenize function to pass the doctests you need to modify it to convert number strings to actual numbers Heres the updated code python def ... View the full answer