Difference between revisions of "TADM2E 5.9"

From Algorithm Wiki
Jump to: navigation, search
(Created page with "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...")
 
 
(2 intermediate revisions by the same user not shown)
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 class Literal implements Node {
−
  return oper(Opr.MINUS, left, right);
+
        int val;
−
  }
 
  
−
  static Node div(Node left, Node right) {
+
        Literal(int val) {
−
  return oper(Opr.DIVIDE, left, right);
+
            this.val = val;
−
  }
+
        }
 +
 
 +
        @Override
 +
        public int evaluate() {
 +
            return val;
 +
        }
 +
    }
 +
 
 +
    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 Node mult(Node left, Node right) {
 
−
  return oper(Opr.MULTIPLY, left, right);
 
−
  }
 
−
 
 
 
}
 
}
  

Latest revision as of 20:33, 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 class Literal implements Node {
        int val;

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

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

    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();
        }
    }

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