150. Evaluate Reverse Polish Notation

Posted on | Edited on | Views:

https://leetcode.com/problems/evaluate-reverse-polish-notation/

Reverse Polish Notation: construct tree with postorder tranversal using stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Node {
    String op;
    Node left;
    Node right;
    Node(String op){this.op=op;left=null;right=null;}
}
class Solution {
    final String NUMBERS="0123456789";

    public int evalRPN(String[] tokens) {
        LinkedList<Node> stack=new LinkedList<>();
        for(String op:tokens){
            Node node=new Node(op);
            if("+-*/".indexOf(op)!=-1){
                node.right=stack.pop();
                node.left=stack.pop();
            }
            stack.push(node);
        }
        return computation(stack.pop());
    }
    
    public int computation(Node node){
        if(node.left==null&&node.right==null) return Integer.valueOf(node.op);
        if(NUMBERS.indexOf(node.left.op)!=-1&&NUMBERS.indexOf(node.right.op)!=-1){
            switch(node.op){
                case "+": return Integer.valueOf(node.left.op)+Integer.valueOf(node.right.op);
                case "-": return Integer.valueOf(node.left.op)-Integer.valueOf(node.right.op);
                case "*": return Integer.valueOf(node.left.op)*Integer.valueOf(node.right.op);
                case "/": return Integer.valueOf(node.left.op)/Integer.valueOf(node.right.op);
            }
        }
        // node.op=="+-*/" can't pass leetcode OJ, 
        // should use deep comparison (.euqals() method) instead.
        if(node.op.equals("+"))return computation(node.left)+computation(node.right);
        else if(node.op.equals("-"))return computation(node.left)-computation(node.right);
        else if(node.op.equals("*"))return computation(node.left)*computation(node.right);
        else return computation(node.left)/computation(node.right);
    }
}

0%