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.
Don't use eval, it will cause runtime error.
Don't use match, it will also cause runtime error.
Template for the expression tree node:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = righInput
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.