Different Ways to Add Parentheses -- Leetcode

Question:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

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]

https://leetcode.com/problems/different-ways-to-add-parentheses/

Answer:

public class Solution {
    public Integer compute(Integer a, Integer b, char op){
        if(op=='+') return a+b;
        else if(op=='-')return a-b;
        else if(op=='*')return a*b;
        return 0;
    }
   
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
        int len = input.length();
       
        if(Character.isDigit(input.charAt(0))){
                int i=0;
                int number = input.charAt(i) - '0';
                while(i+1<len && Character.isDigit(input.charAt(++i))){
                    number = number*10 + input.charAt(i)-'0';
                }
                      //edge case for recusrion, input is just a number, no operator.
                if(i==len-1){
                    res.add(number);
                    return res;
                }
        }
   
           //recursion dp, res(i,j) = res(i,k) op res(k+2,j), op = input[k+1].
        for(int k=0;k<len;++k){
             if(Character.isDigit(input.charAt(k)) == false){
                 List<Integer> left = new ArrayList<Integer>();
                 List<Integer> right = new ArrayList<Integer>();
               
                 left = diffWaysToCompute(input.substring(0,k));
                 right = diffWaysToCompute(input.substring(k+1));
               
                 for(int i=0;i<left.size();++i){
                     for(int j=0;j<right.size();++j){
                         char op = input.charAt(k);
                         Integer subres = compute(left.get(i), right.get(j), op);
                         res.add(subres);
                     }
                 }
             }
        }
        return res;
    }
}

Basic Calculator -- Leetcode

Question:

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Answer:

public class Solution {  

    // "1 + 1 = 2"  

    public int calculate(String s) {  

        if(s==null || s.length() == 0) return 0;  

        

        int res = 0;

        int sign = 1;

        int len = s.length();

        Stack<Integer> stack = new Stack<Integer>();

        

        for(int i=0;i<len;++i){

            char c = s.charAt(i);

            if(Character.isDigit(c)){

                       //calculate number here.

               int number = 0;

               number = c-'0';

               while(i+1<len && Character.isDigit(s.charAt(i+1))){

                   number = number*10 + s.charAt(++i) - '0';

               }

               res = res + sign * number;

            }

            else if(c=='+'){

               sign = 1;

            }

            else if(c=='-'){

               sign = -1;

            }

            else if(c=='('){

                stack.push(res);

                stack.push(sign);

                       //recalculate in the '(xxx)' wrapper now.

                res=0;

                sign=1;

            }

            else if(c==')'){

                if(stack.empty()==false){

                    sign = stack.pop();

                }

                if(stack.empty()==false){

                    res = stack.pop() + sign * res;

                }

            }

        }

        return res;

    }  

} 

Basic Calculator II -- Leetcode

Question:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Answer:
[java]

public class Solution {
    //"3+2*2=7
    public int calculate(String s) {
        if(s==null || s.length() == 0) return 0;

        int len = s.length();
        int res = 0, sign = 1, term = 1, number = 0;
        char op ='+';
        Stack<Integer> stack = new Stack<Integer>();
     
        for(int i=0;i<len;++i){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                //calculate number for current operand.
               number = c-'0';
               while(i+1<len && Character.isDigit(s.charAt(i+1))){
                   number = number*10 + s.charAt(++i) - '0';
               }
             
               if(op=='+' || op=='-'){
                   term = number;
               }
               else if(op=='*'){
                   term *= number;
               }
               else if(op=='/'){
                   term /= number;
               }
            }
            else if(c=='+'){
                res = res + sign * term;
                op = '+';
                sign = 1;
            }
            else if(c=='-'){
                res = res + sign * term;
                op='-';
                sign = -1;
            }
            else if(c=='*'){
                op = '*';
            }
            else if(c=='/'){
                op = '/';
            }
        }
        //calculate for the final res at last step.
        res = res + sign * term;
        return res;
    }
}


[C++]
class Solution { public: int calculate(string s) { istringstream in(s + "+"); long long total = 0, term, sign = 1, n; in >> term; char op; while (in >> op) { if (op == '+' || op == '-') { total += sign * term; sign = 44 - op; //op == '+' ? 1 : -1 in >> term; } 
else { in >> n; if (op == '*') term *= n; else term /= n; } } return total; } };