Description

This problem involves processing a prefix expression by constructing its syntax tree. The syntax tree is built using a base class STNode and two derived classes: OperandNode (for operands) and OperatorNode (for operators).

The program should:

1. Convert the given prefix expression into its equivalent postfix expression by performing a postorder traversal of the syntax tree
2. Evaluate the prefix expression using the provided values for variables A to Z

Your tasks are:

1. Override the printNode() and eval() functions in the derived classes
   • There are three operators, &, | and ^, which represent bitwise AND, bitwise OR and bitwise XOR, respectively
2. Implement the destructor of class OperandNode and OperatorNode to properly delete all nodes in the tree
3. Implement makeNode(char) of both derived classes
   • In OperandNode, the function should take name (the variable name) as input
   • In OperatorNode, the function should take op (the operator) as input
4. Overload the << operator to enable printing a node using cout

Hint: How to overload "cout <<" to print anything?
Hint: You may get RE or MLE if the destructor is not implemented correctly

Input

The first line contain one integer $T$, representing the total number of testcases.

Following $2T$ lines, each testcase consists of $2$ lines

• The first line contains 26 integers, representing the values of variables A to Z, respectively.
• The second line contains a string $S$, representing a prefix expression

Constraints

• $1 \leq T \leq 1000$
• $\text{Sum of }|S| \leq 5 \cdot 10^5$
• Variable name is a single capital alphabet

Output

For each test case, output exactly two lines:

1. The first line should display the postfix expression converted from the given prefix expression.
2. The second line should display the evaluated result of the prefix expression.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14616.cpp

Partial Judge Header

14616.h

Tags

Discuss