SWEA 1232四則演算
40979 ワード
「+、-、*、/」および正の整数からなる任意のバイナリツリーが与えられると、記述プログラムは計算結果を出力する.
質問リンク
バイナリツリー
任意の頂点に演算子がある場合は、その演算子の左/右サブツリーの値を使用して演算します.
中間過程において、演算は実数演算であり、最終結果値は整数部分のみ出力される
問題を見る考え😌
ノードの値が4つの演算子か数値かを決定する必要があります.
ノードのキー値読み出し方式は後続のナビゲーションとして使用できますか?
通過コード😆
比較オブジェクトひかくおぶじぇくと:値(value)あたいvalue
オブジェクトの比較:(を参照)オブジェクトのアドレス
四則演算の計算はもっと簡単にできますか? 他のかっこいい人のハーモニー
keyは、パラメータを受信した関数、iterableの各要素から比較キーを抽出するために使用されます.
反転して位置合わせの方向を決定します.
4つの演算を実行する関数を定義します(
演算にのみ使用される関数を個別に定義すると、コードの分割に役立つようです.
でディクシャナリーに近づくのは貴重な時間だと知っていますが、ほほほ
質問リンク
バイナリツリー
任意の頂点に演算子がある場合は、その演算子の左/右サブツリーの値を使用して演算します.
中間過程において、演算は実数演算であり、最終結果値は整数部分のみ出力される
ノードの値が4つの演算子か数値かを決定する必要があります.
ノードのキー値読み出し方式は後続のナビゲーションとして使用できますか?
def operator(num1, num2, oper):
if oper == "+":
return num1 + num2
elif oper == "-":
return num1 - num2
elif oper == "*":
return num1 * num2
else:
return num1 / num2
# 후위 탐색 과정
def postorder(node_idx):
if 1 <= node_idx <= N:
# 현재 노드의 값이 사칙연산이라면?
if type(tree[node_idx]) is str:
left_value = postorder(left[node_idx])
right_value = postorder(right[node_idx])
# 현재 노드의 키값을 연산자에서 결과값으로 변경
tree[node_idx] = operator(left_value, right_value, tree[node_idx])
return tree[node_idx]
# 10개의 테스트 케이스
for tc in range(1, 11):
# N: 노드의 개수
N = int(input())
# 값을 담을 tree 배열 정의
tree = [0] * (N + 1)
# 연결 관계를 담을 배열 정의 (완전 이진 트리가 아니므로)
left = [0] * (N + 1)
right = [0] * (N + 1)
# 트리 값 및 연결 관계 저장
for _ in range(N):
idx, value, *arg = input().split()
idx = int(idx)
if value in "+-*/":
left[idx] = int(arg[0])
right[idx] = int(arg[1])
else:
value = int(value)
tree[idx] = value
# 루트 노드 값 구하기
result = postorder(1)
print(f"#{tc} {int(result)}")
条件文でtypeを使用する場合、is
演算子を使用できます. if type(value) == str:
pass
if type(value) is str:
pass
==
演算子(Equality)比較オブジェクトひかくおぶじぇくと:値(value)あたいvalue
is
演算子(Identity)オブジェクトの比較:(を参照)オブジェクトのアドレス
l1 = [1, 2, 3]
l2 = [1, 2, 3]
l3 = l1
if l1 == l2:
print("==")
else:
print("!=")
if l1 is l2:
print("is")
else:
print("is not")
if l1 is l3:
print("is")
else:
print("is not")
# 출력값
==
is not
is
完全なバイナリツリーではなくバイナリツリーでナビゲートするには、左/右配列などの接続関係を表すリポジトリが必要です. def operator(num1, num2, oper):
if oper == '-':
return num1 - num2
elif oper == '+':
return num1 + num2
elif oper == '*':
return num1 * num2
else:
return num1 / num2
for tc in range(1,11):
N = int(input())
depth = len(bin(N)) - 2
tree = [0] * (1<<depth)
command = {}
for _ in range(N):
x = list(input().split())
if len(x) == 4:
# 연산자는 딕셔너리에 담고
command[x[0]] = x[1:]
else:
# 숫자는 트리에 바로 담는다.
tree[int(x[0])] = int(x[1])
# key의 역순으로 정렬하여, 계산 진행 (멋지다..ㅠ)
for node in sorted(command.keys() , key = lambda x: int(x), reverse = True):
child1, child2 = tree[int(command[node][1])], tree[int(command[node][2])]
tree[int(node)] = operator(child1, child2, command[node][0])
print('#{} {}'.format(tc, int(tree[1])))
bin()
整数を「0 b」の前のバイナリ文字列に変換します. # 노드의 개수를 알고 있을 때, 트리의 높이를 구하는 방법
# N이 6일 때를 가정해보자.
>> bin(6)
>> "ob110"
# ob가 붙은 이진 문자열이기 때문에 실질적인 이진 문자열은 뒤에 3자리이다.
>> len(bin(6)) - 2
>> 3
sorted(iterable, key=None, reverse=False)
iterableのアイテムの新しいソートリストを返します.keyは、パラメータを受信した関数、iterableの各要素から比較キーを抽出するために使用されます.
反転して位置合わせの方向を決定します.
4つの演算を実行する関数を定義します(
operator
)演算にのみ使用される関数を個別に定義すると、コードの分割に役立つようです.
T = 10
for tc in range(1, T + 1):
N = int(input())
# index를 맞추기 위해 [0]을 0번 인덱스에 삽입
arr= [[0]]
tree = [None] * (N + 1)
for i in range(1, N + 1):
# 각 노드의 정보를 arr 배열에 저장
arr += [list(input().split())]
# 사칙연산이 아닌 경우, tree에 값을 바로 넣어준다.
if len(arr[i]) == 2:
tree[int(arr[i][0])] = int(arr[i][1])
# arr을 역순으로 탐색 (하위 tree에는 이미 숫자 값들이 존재하기에)
for i in range(N, 0, -1):
# 현재 살펴보고 있는 노드의 값이 사칙연산이라면, 값을 계산하여 tree에 저장
if len(arr[i]) != 2:
a0, a1, a2, a3 = int(arr[i][0]), arr[i][1], int(arr[i][2]), int(arr[i][3])
if a1 == '+':
tree[a0] = tree[a2] + tree[a3]
elif a1 == '-':
tree[a0] = tree[a2] - tree[a3]
elif a1 == '*':
tree[a0] = tree[a2] * tree[a3]
else:
tree[a0] = tree[a2] / tree[a3]
print('#{} {}'.format(tc, int(tree[1])))
T = 10
for test_case in range(1, T + 1):
N = int(input())
dic_c = {}
li_tree = [-1 for _ in range(N + 1)]
for i in range(N):
li_tmp = list(input().split())
# 사칙연산인 경우
if len(li_tmp) == 4:
node, op, c1, c2 = li_tmp
node, c1, c2 = int(node), int(c1), int(c2)
# 해당 노드의 인덱스를 key로 하고, 자식 노드의 인덱스를 튜플로 value에 저장
dic_c[node] = (c1,c2)
# 트리에 연산자를 저장
li_tree[node] = op
# 숫자인 경우
else:
node, value = li_tmp
node, value = int(node), int(value)
# 트리에 숫자를 저장
li_tree[node] = value
# 딕셔너리를 key의 역순(바닥부터 올라오도록)으로 정렬하여, 결과값을 트리에 저장
for i in sorted(dic_c.keys(), reverse=True):
if li_tree[i] == '+':
li_tree[i] = li_tree[dic_c[i][0]] + li_tree[dic_c[i][1]]
elif li_tree[i] == '-':
li_tree[i] = li_tree[dic_c[i][0]] - li_tree[dic_c[i][1]]
elif li_tree[i] == '*':
li_tree[i] = li_tree[dic_c[i][0]] * li_tree[dic_c[i][1]]
elif li_tree[i] == '/':
li_tree[i] = li_tree[dic_c[i][0]] // li_tree[dic_c[i][1]]
print(f'#{test_case} {int(li_tree[1])}')
Reference
この問題について(SWEA 1232四則演算), 我々は、より多くの情報をここで見つけました https://velog.io/@byunghun-jake/SWEA1232사칙연산テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol