Alibi

My Life is Getting Better

Leetcode[150] Evaluate Reverse Polish Notation

13 Nov 2015

###Task1 Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples: [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9

[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

###Python ####Java way

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        if not tokens or len(tokens) == 0:
            return 0
        stack = []
        op = '+-*/'
        for s in tokens:
            if s not in op:
                stack.append(int(s))
            else:
                first = stack.pop()
                second = stack.pop()
                opInd = op.index(s)
                if opInd == 0:
                    stack.append(first + second)
                elif opInd == 1:
                    stack.append(second - first)
                elif opInd == 2:
                    stack.append(first * second)
                elif opInd == 3:
                    stack.append(int(second * 1.0 / first))
        return stack.pop()

####Lambda magic

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        if not tokens or len(tokens) == 0:
            return 0
        stack = []
        op = '+-*/'
        for s in tokens:
            if s not in op:
                stack.append(int(s))
            else:
                first = stack.pop()
                second = stack.pop()
                stack.append(self.calcu(second, first, s))
        return stack.pop()
        
    def calcu(self, a, b, s):
        op_dict = { '+' : lambda x, y: x + y,
                    '-' : lambda x, y: x - y,
                    '*' : lambda x, y: x * y,
                    '/' : lambda x, y: int(1.0 * x / y),
                   }
        return op_dict[s](a, b)

###Java

import java.util.*;

public class Solution {

    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
        	return 0;
        }
        String operator = "+-*/";
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < tokens.length; i++) {
        	if (!operator.contains(tokens[i])) {
        		stack.push(tokens[i]);
        	} else {
        		int a = Integer.parseInt(stack.pop());
        		int b = Integer.parseInt(stack.pop());

        		switch(tokens[i]) {
        			case "+":
        				stack.push(String.valueOf(b + a));
        				break;
        			case "-":
        				stack.push(String.valueOf(b - a));
        				break;
        			case "*":
        				stack.push(String.valueOf(b * a));
        				break;
        			case "/":
        				stack.push(String.valueOf(b / a));
        				break;
        			default:
        				break;
        		}
        	}
        }

        return Integer.parseInt(stack.pop());
    }

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	String[] tokens = {"4", "13", "5", "/", "+"};
    	System.out.println(sol.evalRPN(tokens));
    }
}

###Points

Related Posts