Different ways to add parenthesis

Problem : Given a string of numbers and operators return all possible results from computing all the different possible ways to group numbers and operators, all the valid operators are '+',  '-',  '*'.
Basic Idea is to start from left and move towards right recursively while calculating the result of every pair bases on the operator in between them. for ex :
(2-(1-1))
(2-1) -1)
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

public class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> result = new ArrayList<Integer>(); for(int i = 0;i < input.length(); i++){ if(input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){ List<Integer> left = diffWaysToCompute(input.substring(0,i)); List<Integer> right = diffWaysToCompute(input.substring(i+1)); for(int j = 0; j < left.size(); j++){ for(int k = 0; k < right.size(); k++){ switch (input.charAt(i)){ case '+' : result.add(left.get(j) + right.get(k)); break; case '-' : result.add(left.get(j) - right.get(k)); break; case '*' : result.add(left.get(j) * right.get(k)); break; default : break; } } } } } if(result.size() == 0 ){ result.add(atoi(input)); } return result; } public static int atoi(String str) { if (str == null || str.length() < 1) return 0; // trim white spaces str = str.trim(); char flag = '+'; // check negative or positive int i = 0; if (str.charAt(0) == '-') { flag = '-'; i++; } else if (str.charAt(0) == '+') { i++; } // use double to store result double result = 0; // calculate value while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') { result = result * 10 + (str.charAt(i) - '0'); i++; } if (flag == '-') result = -result; // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE; return (int) result; } }

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Basic idea is to scan the string from left to right and push left parenthesis in a stack and pop them whenever a right parenthesis is encountered and check for valid pair, If its not a valid pair then return false. At the end of the scan, stack should be empty as all left parenthesis should have been popped out to match for valid pairs with right pantheists. 

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 41 42 43 44 45 46 47 48

public class Solution { public boolean isValid(String s) { if(s == null || s.length() <2 ){ return false; } Stack stack = new Stack(); for(int i=0; i < s.length(); i++){ if(isLeftParanthesis(s.charAt(i)) ){ stack.push(s.charAt(i)); }else if(isRightParanthesis(s.charAt(i))){ if(!stack.isEmpty()){ char top = (char)stack.pop(); if(!isValidPair(top,s.charAt(i))){ return false; } }else{ return false; } } } if(!stack.isEmpty()){ return false; } return true; } public boolean isLeftParanthesis(char c){ return (c == '(' || c == '{' || c == '['); } public boolean isRightParanthesis(char c){ return (c == ')' || c == '}' || c == ']'); } public boolean isValidPair(char c1, char c2){ if(c1 == '(' && c2 == ')'){ return true; } if(c1 == '{' && c2 == '}'){ return true; } if(c1 == '[' && c2 == ']'){ return true; } return false; } }