3274 - I2P(I)2025_Chou_Hu_Hw8_ClassB Scoreboard

Time

2025/11/25 20:30:00 2025/12/02 18:30:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team
# Problem Pass Rate (passed user / total user)
14837 Expression Tree Conversion
14845 File Tree

14837 - Expression Tree Conversion   

Status  |  Limits Submit

Description

Lawrence and Holo are traveling merchants who journey from town to town, trading goods to earn their profit.

For merchants like them, the most important thing is calculating money correctly.

To avoid any mistakes, they write every arithmetic expression in fully parenthesized form.

However, another crucial part of business is reducing costs.

Too many parentheses waste ink on their account books, so they hope you can help them convert each expression into prefix (preorder) form, which conveys the same meaning without needing any parentheses.

You are given a single arithmetic expression in fully parenthesized infix form.

The expression consists of:

  • positive integer (possibly multi-digit)
  • binary operators +, -, *, and /
  • parathsis ( and )

Your have to build the corresponding expression tree, print the preorder of the expression tree, and evaluate the result of the expression.

Reminder

Round every division you encounter using //.

Fully parenthesized form means that every binary operation is wrapped in parentheses.

Template for the expression tree node:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = righ

Input

The input consists of a single line, a fully parenthesized infix expression $E$.

It is guaranteed that you won't encounter divided by zero for all testcase.

Output

Output exactly two lines:

  • Line 1: The preorder of the expression, operators and numbers must be separated by a single space.
  • Line 2: A single integer – the evaluated result of the expression.

Sample Input  Download

Sample Output  Download




Discuss




14845 - File Tree   

Status  |  Limits Submit

Description

Terminology

  • A file tree is a tree structure that organizes files and directories (folders).
  • At the top, there is a special directory called the root directory, written as /.
  • Current working directory, means the directory you are currently at.
  • A path describes how to reach a file or a directory, you can refer to 02-basic-computing page 13 for more information about absolute path and relative path.

Task description

  • You have to implement a file tree.
  • You start from an empty file tree that only has a single root directory /.
  • You will then receive a sequence of commands, and you need to process the commands in order, update the file tree, and print the outputs of some commands.

Notices

  • EXAMPLE in the following decription are the extra sample. You can test them manualy by setting DEBUG_MODE to True.
    • The command after > is the input.
    • The path before > is the current working directory.
  • All the PATH mentioned in the following can be an absolute path or a relative path.
  • We have modified or simplified some commands for convenience, so some details might be different from the the os module or a real file system, try not to mix them up.

TODO function

  • path_to_nodes(PATH)
    • Given a path, you have to return the absoulte path in a list of nodes List[Node].
    • If PATH does not exist, return None.

TODO commands

  • cd PATH
    • Functionality:
      • Change the current working directory to PATH.
    • Exception:
      • If PATH does not exist or is not a directory, do nothing.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      /A/C
      Commands start here:
      / > cd ..                # Already in /, do nothing
      / > cd ./A 
      /A > cd B
      /A/B > cd ..
      /A > cd /D                     # Directory D does not exist, do nothing
      /A > cd /A/C
      /A/C >
  • ls
    • Functionality:
      • Print the names of all direct children (files and directories) in lexicographical order in a single line.
      • Every names are separated by a single space (No additional space after last one).
    • Exception:
      • If the directory is empty, print an empty line.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      /A/e
      /A/Z
      Commands start here:
      / > ls
      A
      / > cd A
      /A > ls
      B Z e
      /A > cd B
      /A/B > ls

      /A/B >
  • touch PATH
    • PATH can be decomposed into {PARENT_PATH, FILE_NAME}.
    • Functionality:
      • Create a file named FILE_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH  does not exist or is not a directory, do nothing.
      • If a file or a directory named FILE_NAME already exists under PARENT_PATH directory, do nothing.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      Commands start here:
      / > cd A
      /A > touch hi             #       File /A/hi is created
      /A > touch /A/B/sus       # File /A/B/sus is created
      /A > touch /C/no          # /C does not exist, do nothing
  • rm PATH
    • PATH can be decomposed into {PARENT_PATH, FILE_NAME}
    • Functionality:
      • Remove a file named FILE_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
      • If FILE_NAME does not exists under PARENT_PATH directory, do nothing.

    • EXAMPLE

    • Current existing directories and files:
      /
      /A
      /A/B
      /A/f (file)
      /A/g (file)
      Commands start here:
      / > cd A
      /A > rm /A/f             # File /A/f is removed
      /A > rm ./g              #       File /A/g is removed
      /A > rm B                # /A/B is not a file, do nothing

Template

  • class Node
    • Each node represents a directory or a file in the file tree.
  • mkdir PATH
    • PATH can be decomposed into {PARENT_PATH, DIR_NAME}
    • Functionality:
      • Create a directory named DIR_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
      • If a file or a directory named DIR_NAME already exists under PARENT_PATH directory, do nothing.
import sys

class Node:
    def __init__(self, name, is_dir, parent=None):
        self.name = name
        self.is_dir = is_dir
        self.parent = parent
        self.children = {}

class FileTree:
    def __init__(self):
        self.root = Node("/", True, None)
        self.cwd = self.root
   
    # !!! You can add more functions if needed !!! #
   
    def path_to_nodes(self, path):
        # TODO
        pass

    def mkdir(self, path):
        if path.endswith('/') and len(path) > 1:
            path = path[:-1]
        idx = path.rfind('/')
        if idx == -1:
            p_path, name = ".", path
        elif idx == 0:
            p_path, name = "/", path[1:]
        else:
            p_path, name = path[:idx], path[idx+1:]
        nodes = self.path_to_nodes(p_path)
        if nodes:
            parent = nodes[-1]
            if parent.is_dir and name not in parent.children:
                parent.children[name] = Node(name, True, parent)

    def cd(self, path):
        # TODO
        pass

    def ls(self):
        # TODO
        pass

    def touch(self, path):
        # TODO
        pass

    def rm(self, path):
        # TODO
        pass

    # Debug functions
    def print_prompt(self):
        nodes = self.path_to_nodes(".")
        path_str = "/" + "/".join([n.name for n in nodes[1:]])
        if path_str.endswith("/") and len(path_str) > 1: path_str = path_str[:-1]
        print(f"{path_str} >", end=" ", flush=True)

    def print_all(self, node=None, prefix=""):
        if node is None: node, prefix = self.root, ""
        current = prefix + ("/" + node.name if node != self.root else "")
        print(current if node.is_dir else f"{current} (file)")
        if node.is_dir:
            for k in sorted(node.children): self.print_all(node.children[k], current)

def main():
    ft = FileTree()
    # !!! Enable debug mode here !!!
    # !!! Remember to disable it when submitting !!!
    DEBUG_MODE = True
    
    while True:
        if DEBUG_MODE: ft.print_prompt()
        try:
            line = sys.stdin.readline()
            if not line:
                if DEBUG_MODE: print()
                break
        except: break

        line = line.strip()
        if not line: continue

        p = line.split()
        cmd, args = p[0], p[1:]

        if   cmd == 'mkdir' and len(args)==1: ft.mkdir(args[0])
        elif cmd == 'cd'    and len(args)==1: ft.cd(args[0])
        elif cmd == 'ls'    and len(args)==0: ft.ls()
        elif cmd == 'touch' and len(args)==1: ft.touch(args[0])
        elif cmd == 'rm'    and len(args)==1: ft.rm(args[0])
        elif cmd == 'print_all':              ft.print_all()

        if DEBUG_MODE and cmd != 'ls':
            print("--- Tree ---"); ft.print_all(); print("------------")

if __name__ == "__main__":
    main()

​

Input

  • Each line contains a single command.
  • Command names and arguments are separated by a single space.
  • Paths never contain spaces.
  • File and directory names consist only of letters and digits.
  • Input is read until EOF.

Output

Only the following command produce output:

  • ls
    • Print the names of all direct children (files and directories) in lexicographical order.
    • Print all names on one line, separated by a single space. (No additional space after last one)
    • If the directory is empty, print an empty line.

Sample Input  Download

Sample Output  Download




Discuss