TADM2E 5.9 - Revision history

Kfuwowurm at 20:33, 18 August 2016

2016-08-18T20:33:18Z

Kfuwowurm at 20:23, 18 August 2016

2016-08-18T20:23:53Z

Kfuwowurm at 16:21, 6 August 2016

2016-08-06T16:21:57Z

Kfuwowurm: 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..."

2016-08-06T16:18:41Z

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..."

New page

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:

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

}

</nowiki>

@@ Line 15: / Line 15: @@
      static interface Node {
          int evaluate();
+     }
@@ Line 68: / Line 81: @@
          public int evaluate() {
              return operand1.evaluate() / operand2.evaluate();
+         }
+     }

@@ Line 6: / Line 6: @@
   <nowiki>
 class Main {
-  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));
-  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;
+}

@@ Line 9: / Line 9: @@
    static int evaluate(Node node) {
    	if (node.left == null) { //it's a literal
-           assert node.right == null && node.opr == null;
+                assert node.right == null && node.opr == null;
-           return node.num.intValue();
+                return node.num.intValue();
+   	}
@@ Line 58: / Line 58: @@
    	Node test3 = plus(literal(2),mult(literal(3),literal(4)));
-    System.out.println(evaluate(test1));
+        System.out.println(evaluate(test1));
-    System.out.println(evaluate(test2));
+        System.out.println(evaluate(test2));
-    System.out.println(evaluate(test3));
+        System.out.println(evaluate(test3));
+   }