from typing import List


def getMostImportantOpIndex(parts: List[str]) -> int:
    """Returns the index of the most important operator in the given list of parts."""
    index = len(parts) + 1
    higher_order_operator = 0

    if "^" in parts:
        higher_order_operator = 2
        index = parts.index("^")
    if "*" in parts and higher_order_operator < 2 and parts.index("*") < index:
        higher_order_operator = 1
        index = parts.index("*")
    if "/" in parts and higher_order_operator < 2 and parts.index("/") < index:
        higher_order_operator = 1
        index = parts.index("/")
    if "%" in parts and higher_order_operator < 2 and parts.index("%") < index:
        higher_order_operator = 1
        index = parts.index("%")
    if "+" in parts and higher_order_operator < 1 and parts.index("+") < index:
        index = parts.index("+")
    if "-" in parts and higher_order_operator < 1 and parts.index("-") < index:
        index = parts.index("-")
    return index


def runStep(a: str, sign: str, b: str) -> str:
    """Runs a single step of the evaluation process."""
    if sign == "+":
        return str(int(a) + int(b))
    elif sign == "-":
        return str(int(a) - int(b))
    elif sign == "*":
        return str(int(a) * int(b))
    elif sign == "/":
        return str(int(a) // int(b))
    elif sign == "%":
        return str(int(a) % int(b))
    elif sign == "^":
        return str(int(a) ** int(b))
    else:
        raise ValueError("Invalid operator")


def getEvalSteps(expr: str) -> str:
    """Returns a string containing the evaluation steps of the given expression."""
    padding = " " * (len(expr) + 1) + "= "

    expr = expr.strip()
    expr = expr.replace(" ", "")
    expr = expr.replace("**", "^")
    expr = expr.replace("//", "/")
    steps = [expr]

    expr_parts = []
    cur_piece = ""
    for c in expr:
        if c.isdigit():
            cur_piece += c
        else:
            expr_parts.append(cur_piece)
            expr_parts.append(c)
            cur_piece = ""
    expr_parts.append(cur_piece)
    while len(expr_parts) > 1:
        next_op = getMostImportantOpIndex(expr_parts)
        left = expr_parts.pop(next_op - 1)
        op = expr_parts.pop(next_op - 1)
        right = expr_parts.pop(next_op - 1)
        val = runStep(left, op, right)
        expr_parts.insert(next_op - 1, val)
        steps.append("".join(expr_parts))
    steps[0] = steps[0] + " = " + steps.pop(1)
    steps = [step.replace("^", "**") for step in steps]
    steps = [step.replace("/", "//") for step in steps]
    steps = [padding + step if not i == 0 else step for i, step in enumerate(steps)]
    final = "\n".join(steps) + "\n"
    return final


def testGetEvalSteps():
    print("Testing getEvalSteps()...", end="")
    assert (
        getEvalSteps("2+3*4-8**3%3")
        == """\
2+3*4-8**3%3 = 2+3*4-512%3
             = 2+12-512%3
             = 2+12-2
             = 14-2
             = 12
"""
    )
    assert (
        getEvalSteps("2**2**3+4-2//3")
        == """\
2**2**3+4-2//3 = 4**3+4-2//3
               = 64+4-2//3
               = 64+4-0
               = 68-0
               = 68
"""
    )
    assert (
        getEvalSteps("4//2**2*8-3+2")
        == """\
4//2**2*8-3+2 = 4//4*8-3+2
              = 1*8-3+2
              = 8-3+2
              = 5+2
              = 7
"""
    )
    assert (
        getEvalSteps("2**4//2-3+1")
        == """\
2**4//2-3+1 = 16//2-3+1
            = 8-3+1
            = 5+1
            = 6
"""
    )
    print("Passed!")


testGetEvalSteps()