# 2013春　逆ポーランド技法

def get_priority(element):
    # 表2：演算要素の優先度
    priorities = {
        '(': 5,
        '数値': 4,
        '*': 3, '/': 3,  # ア, イ
        '+': 2, '-': 2,  # ウ, エ
        ')': 1
    }
    if isinstance(element, int) or element.isdigit():
        return priorities['数値']
    return priorities.get(element, 0) # nullの場合は0を返す

def convert_to_rpn(formula):
    # 初期設定
    result = [None] * 100  # result[]: 変換後配列
    resultCount = 0
    stack = [None] * 100   # stack[]: スタック用配列
    stackCount = 1

    # 図2: stack[stackCount] ← null
    stack[stackCount] = "null"

    elementCount = len(formula)
    i = 1 # 変換前配列のインデックス（1から開始）

    # 図2: while (i が elementCount 以下の間繰り返す)
    while i <= elementCount:
        current_element = formula[i-1] # Pythonの0始まりを調整
        elementPriority = get_priority(current_element)

        # キ: stackTop ← stack[stackCount]
        stackTop = stack[stackCount]

        # ク: while (GetPriority(stackTop) >= elementPriority かつ stackTop が "(" 以外)
        while get_priority(stackTop) >= elementPriority and stackTop != "(":
            resultCount += 1
            result[resultCount] = stackTop # 変換後配列の末尾に追加
            stackCount -= 1
            stackTop = stack[stackCount] # キ: stackTop ← stack[stackCount]

        # 演算要素を処理する
        # ケ: if (GetElement(i) が ")" に等しい)
        if current_element == ")":
            stackCount -= 1 # "(" をポップして破棄
        else:
            stackCount += 1
            stack[stackCount] = current_element # スタックにプッシュ

        i += 1

    # 図2最後: スタックに残った要素を変換後配列に追加
    # キ: while (stack[stackCount] が null でない間)
    while stack[stackCount] != "null":
        resultCount += 1
        result[resultCount] = stack[stackCount]
        stackCount -= 1

    # 1から始まる配列をPythonのリスト形式に整えて返す
    return [result[j] for j in range(1, resultCount + 1)]

# テスト実行：1 + 2 * 3
formula_input = ["1", "+", "2", "*", "3"]
print(f"入力: {formula_input}")
print(f"出力: {convert_to_rpn(formula_input)}")

# 設問1(1)のテスト：( 2 + 3 ) * 4
formula_q1 = ["(", "2", "+", "3", ")", "*", "4"]
print(f"設問1(1): {formula_q1}")
print(f"結果: {convert_to_rpn(formula_q1)}")