Difference between revisions of "TADM2E 5.9"

From Algorithm Wiki
Jump to: navigation, search
Line 6: Line 6:
 
  <nowiki>
 
  <nowiki>
 
class Main {
 
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) {
+
    public static void main(String[] args) {
−
  return new Node(opr, null, left, right);
+
        Node expression = new Addition(new Addition(new Literal(1), new Literal(2)),
−
  }
+
                new Literal(3));
 +
        System.out.println(expression.evaluate());
 +
    }
  
−
  static Node plus(Node left, Node right) {
+
    static interface Node {
−
  return oper(Opr.PLUS, left, right);
+
        int evaluate();
−
  }
+
    }
  
−
  static Node minus(Node left, Node right) {
+
    static abstract class Op implements Node {
−
  return oper(Opr.MINUS, left, right);
+
        Node operand1;
−
  }
+
        Node operand2;
  
−
  static Node div(Node left, Node right) {
+
        Op(Node operand1, Node operand2) {
−
  return oper(Opr.DIVIDE, left, right);
+
            this.operand1 = operand1;
−
  }
+
            this.operand2 = operand2;
 +
        }
 +
    }
 +
 
 +
    static class Addition extends Op {
 +
        Addition(Node operand1, Node operand2) {
 +
            super(operand1, operand2);
 +
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return operand1.evaluate() + operand2.evaluate();
 +
        }
 +
    }
 +
 
 +
    static class Substraction extends Op {
 +
        Substraction(Node operand1, Node operand2) {
 +
            super(operand1, operand2);
 +
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return operand1.evaluate() - operand2.evaluate();
 +
        }
 +
    }
 +
 
 +
    static class Division extends Op {
 +
        Division(Node operand1, Node operand2) {
 +
            super(operand1, operand2);
 +
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return operand1.evaluate() / operand2.evaluate();
 +
        }
 +
    }
 +
 
 +
    static class Multiplication extends Op {
 +
        Multiplication(Node operand1, Node operand2) {
 +
            super(operand1, operand2);
 +
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return operand1.evaluate() / operand2.evaluate();
 +
        }
 +
    }
 +
 
 +
    static class Literal implements Node {
 +
        int val;
 +
 
 +
        Literal(int val) {
 +
            this.val = val;
 +
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return val;
 +
        }
 +
    }
  
−
  static Node mult(Node left, Node right) {
 
−
  return oper(Opr.MULTIPLY, left, right);
 
−
  }
 
−
 
 
 
}
 
}
  

Revision as of 20:23, 18 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 {

    public static void main(String[] args) {
        Node expression = new Addition(new Addition(new Literal(1), new Literal(2)),
                new Literal(3));
        System.out.println(expression.evaluate());
    }

    static interface Node {
        int evaluate();
    }

    static abstract class Op implements Node {
        Node operand1;
        Node operand2;

        Op(Node operand1, Node operand2) {
            this.operand1 = operand1;
            this.operand2 = operand2;
        }
    }

    static class Addition extends Op {
        Addition(Node operand1, Node operand2) {
            super(operand1, operand2);
        }

        @Override
        public int evaluate() {
            return operand1.evaluate() + operand2.evaluate();
        }
    }

    static class Substraction extends Op {
        Substraction(Node operand1, Node operand2) {
            super(operand1, operand2);
        }

        @Override
        public int evaluate() {
            return operand1.evaluate() - operand2.evaluate();
        }
    }

    static class Division extends Op {
        Division(Node operand1, Node operand2) {
            super(operand1, operand2);
        }

        @Override
        public int evaluate() {
            return operand1.evaluate() / operand2.evaluate();
        }
    }

    static class Multiplication extends Op {
        Multiplication(Node operand1, Node operand2) {
            super(operand1, operand2);
        }

        @Override
        public int evaluate() {
            return operand1.evaluate() / operand2.evaluate();
        }
    }

    static class Literal implements Node {
        int val;

        Literal(int val) {
            this.val = val;
        }

        @Override
        public int evaluate() {
            return val;
        }
    }

}
Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_5.9&oldid=438"