Difference between revisions of "TADM2E 5.9"

Revision as of 16:21, 6 August 2016

You can solve this problem by doing a DFS on the graph. Each node can be an operation or a literal. Literal will be leaves in the graph and operations will always have in this case both children. The recursive function "evaluates" the expression represented by each child node and then calculates the final result by applying the operation represented by the current node.

Here is an implementation in Java:

class Main {
  
  static int evaluate(Node node) {
  	if (node.left == null) { //it's a literal
                assert node.right == null && node.opr == null;
                return node.num.intValue();
  	}
  	
  	int leftOperand = evaluate(node.left);
  	int rightOperand = evaluate(node.right);
  	
  	int result;
  	switch(node.opr) {
  		case PLUS:
  			result = leftOperand + rightOperand;
  			break;
  		case MINUS:
  			result = leftOperand - rightOperand;
  			break;
  		case DIVIDE:
  			result = leftOperand / rightOperand;
  			break;
  		case MULTIPLY:
  			result = leftOperand * rightOperand;
  			break;
  		default:
  			throw new IllegalArgumentException();
  	}
  	return result;
  }
  
  static class Node {
  	Opr opr;
  	Integer num;
  	Node left;
  	Node right;
  	Node(Opr opr, Integer num, Node left, Node right) {
  		this.opr = opr;
  		this.num = num;
  		this.left = left;
  		this.right = right;
  	}
  }
  
  static enum Opr {PLUS, MINUS, DIVIDE, MULTIPLY}
    
    
  //Utils functions and initial testing
  public static void main(String[] args) {
  	Node test1 = literal(2);
  	Node test2 = plus(literal(2), literal(1));
  	Node test3 = plus(literal(2),mult(literal(3),literal(4)));
  	
        System.out.println(evaluate(test1));
        System.out.println(evaluate(test2));
        System.out.println(evaluate(test3));
  }
  
  static Node literal(int num) {
  	return new Node(null, num, null, null);
  }

  static Node oper(Opr opr, Node left, Node right) {
  	return new Node(opr, null, left, right);
  }

  static Node plus(Node left, Node right) {
  	return oper(Opr.PLUS, left, right);
  }

  static Node minus(Node left, Node right) {
  	return oper(Opr.MINUS, left, right);
  }

  static Node div(Node left, Node right) {
  	return oper(Opr.DIVIDE, left, right);
  }

  static Node mult(Node left, Node right) {
  	return oper(Opr.MULTIPLY, left, right);
  }
  
}