I required to implement a simple symbolic equation solver. The equation must be stored in a binary tree. Each operand or operator should be stored as a tuple of the form (TYPE, VALUE).

For example: (OPERAND, 5), (OPERAND, 7), (OPERAND, 34), (OPERATOR, ‘ ’) or (OPERATOR, '*’').

Following operators should be supported: addition ( ), subtraction (-), multiplication (*), and exponentiation (^).

They gave me that sketch. but I couldn't understand to solve this. I should include my code that (#Include your code here) point. anyone can help me with that?

class Node:

    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def get_output(self):
        '''
        Print the output depending on the evaluated value.
        If the 0 <= value <= 999 the value is printed.
        If the value < 0, UNDERFLOW is printed.
        If the value > 999, OVERFLOW is printed.

        :return: None
        '''
        value = self.evaluate()
        if value > 999:
            print('OVERFLOW')
        elif value < 0:
            print('UNDERFLOW')
        else:
            print(value)

    #####################################################################
    ######### Your task is to implement the following methods. ##########
    #####################################################################
    
    def insert(self, data, bracketed):
        '''
        Insert operators and operands into the binary tree.

        :param data: Operator or operand as a tuple. E.g.: ('OPERAND', 34), ('OPERATOR', ‘ ’)
        :param bracketed: denote whether an operator is inside brackets or not. If the operator is inside brackets,
        we set bracketed as True.
        :return: self
        '''
        
        #Include your code here

        
        return self

    def evaluate(self):
        '''
        Process the expression stored in the binary tree and compute the final result.
        To do that, the function should be able to traverse the binary tree.

        Note that the evaluate function does not check for overflow or underflow.

        :return: the evaluated value
        '''
        
        #Include your code here
        pass

CodePudding user response：

enum Operator {
    ADD, SUB, MUL, DIV, POW, NULL
}

class Node {
    int value;
    Operator op;
    Node left;
    Node right;
    
    public Node(int value) {
        this.value = value;
        this.op = Operator.NULL;
        this.left = null;
        this.right = null;
    }
    
    public Node(Operator op) {
        this.value = 0;
        this.op = op;
        this.left = null;
        this.right = null;
    }
    
    public void getOutput() {
        int value = this.evaluate();
        if(value>999) {
            System.out.println("OVERFLOW");
        } else if(value<0) {
            System.out.println("UNDERFLOW");
        } else {
            System.out.println(value);
        }
    }
    
    public Node insert(int data, Operator op, boolean bracketed) {
        Node node;
        if(op==Operator.NULL) { // in this case add to right child or right of the right child
            if(this.right==null) { // currently we are not inside a pair of bracket
                this.right=new Node(data);
                return this;
            }
            this.right.right=new Node(data);
            return this;
        } else { // add as parent or do the switching
            if(bracketed) {
                if(this.right==null) { // if we are having a leading bracket -> (2*4) 3*5 8
                    this.op=op;
                    node=new Node(this.value);
                    this.left=node;
                } else { // if the bracket is a not in the first place
                    Node temp=this.right;
                    temp.op=op;
                    node=new Node(temp.value);
                    temp.left=node;
                }
                return this;
            }
            node=new Node(op);
            node.left=this;
            return node;
        }
    }
    
    public int evaluate() {
        if(this.op==Operator.NULL) { // termination condition
            return this.value;
        }
        int l=this.left.evaluate();
        System.out.println(l);
        int r=this.right.evaluate(); // post order traversal
        System.out.println(r);
        switch (this.op) { // decide which operation to perform
        case ADD:
            return l r;
        case SUB:
            return l-r;
        case MUL:
            return l*r;
        case POW:
            return (int)Math.pow(l, r);
        default:
            return l/r;
        }
    }

    
    // just for visualization purpose
    @Override
    public String toString() {
        return "Node{"   "value="   value   ", op="   op  '}';
    }
}

Try to grab the idea and translate to python