[SW Expert Academy] 1232. Basic Arithmetic Operations

1. Question

Expressions composed of basic arithmetic operations can be represented as binary trees. Below is an example of the expression "(9/(6-4))*3" represented as a binary tree.

If an arbitrary vertex contains an operator, the result of the left subtree and the right subtree of that operator are applied to the operator.

Write a program that calculates and outputs the result of an arbitrary binary tree composed only of the basic arithmetic operations "+, -, *, /" and positive integers.

All calculations during the process should be done as floating-point operations.

[Input]

A total of 10 test cases are given. (The total number of test cases is not given as input)

For each test case, the first line provides the number of vertices N (1≤N≤1000). Over the next N lines, information for each vertex is provided.

If the vertex is an integer, the vertex number and a positive integer are given. If the vertex is an operator, the vertex number, the operator, and the vertex numbers of the left and right children are given in order.

Vertex numbers are distinguished as integers from 1 to N, and the number of the root vertex is always 1.

For example, if the number 4 corresponds to vertex 7, it is given as "7 4". If the operator '/' corresponds to vertex 2, and its two children are the number 9 at vertex 4 and the operator '-' at vertex 5, it is given as "2 / 4 5".

[Output]

For each test case, output '#t' (where t is the test case number, starting from 1) and the result of the arithmetic operation.

The result should be output as an integer, rounding down any decimal places.

2. Thoughts

3. Tips learned

3. Binary Tree

From https://www.educative.io/answers/binary-trees-in-python

Binary Tree
Binary Tree is a form of a tree whose nodes cannot have more than two children. Each node of the binary tree has two pointers associated with it, one points to the left child, and the other points to the right child of the node. It is an unordered tree having no fixed organized structure for the arrangement of nodes.

4. My solution

The reversed() Function

import sys

sys.stdin = open("input.txt", "r")


def solve_arith(Nodes, node):
    if len(Nodes[node]) == 1:
        return int(Nodes[node][0])
    else:
        
        if Nodes[node][0] == '+':
            return solve_arith(Nodes,int(Nodes[node][1])) + solve_arith(Nodes,int(Nodes[node][2]))
        if Nodes[node][0] == '-':
            return solve_arith(Nodes,int(Nodes[node][1])) - solve_arith(Nodes,int(Nodes[node][2]))
        if Nodes[node][0] == '/':
            return solve_arith(Nodes,int(Nodes[node][1])) / solve_arith(Nodes,int(Nodes[node][2]))
        if Nodes[node][0] == '*':
            return solve_arith(Nodes,int(Nodes[node][1])) * solve_arith(Nodes,int(Nodes[node][2]))

    return None



T = 10

for test_case in range(1, T + 1):
    NodeNum = int(input())
    Nodes = [None] * (NodeNum+1)

    for node in range(NodeNum):
        inputs = input().split()
        Nodes[int(inputs[0])] = inputs[1:]
    
    ans = int(solve_arith(Nodes, 1))

    print(f"#{test_case} {ans}")

5. AI Solution and Improvements

Your solution is a good approach to solving the given problem. It uses a recursive function to evaluate the expression represented by the binary tree. Here are some suggestions to improve or optimize your solution:

1. Function Optimization: Your solve_arith function can be optimized for readability and efficiency. Instead of multiple if statements, you could use a dictionary to map operators to their corresponding operations. This makes the function more concise and easier to maintain.

2. Error Handling: Consider adding error handling for cases where the input data might be invalid (e.g., an unknown operator, or referencing a non-existent node).

3. Performance Enhancement: While recursion is a natural fit for this problem, in cases of very deep trees, you might run into stack overflow issues. An iterative approach using a stack can avoid this, although it's more complex to implement.

4. Input Handling: You're currently reading input from a file named "input.txt". Ensure that the file exists and contains the correct format of data to avoid runtime errors.

5. Code Documentation: Adding comments to your code to explain what each part does can be very helpful, especially for more complex logic.

Here's a revised version of your code with some of these suggestions:

import sys

# Replacing sys.stdin for demonstration purposes
# sys.stdin = open("input.txt", "r")

def solve_arith(nodes, node):
    if len(nodes[node]) == 1:
        return int(nodes[node][0])
    else:
        left_result = solve_arith(nodes, int(nodes[node][1]))
        right_result = solve_arith(nodes, int(nodes[node][2]))
        operation = {
            '+': lambda x, y: x + y,
            '-': lambda x, y: x - y,
            '*': lambda x, y: x * y,
            '/': lambda x, y: x / y,
        }.get(nodes[node][0])

        return operation(left_result, right_result) if operation else None

T = 10

for test_case in range(1, T + 1):
    NodeNum = int(input())
    nodes = [None] * (NodeNum + 1)

    for _ in range(NodeNum):
        inputs = input().split()
        nodes[int(inputs[0])] = inputs[1:]

    ans = int(solve_arith(nodes, 1))

    print(f"#{test_case} {ans}")

This code is more readable and handles the operations in a more elegant way. However, the core logic and structure remain similar to your original solution.