LeetCode 227 - Basic Calculator II

LeetCode 224 - Basic Calculator
LeetCode 227 - Basic Calculator II
LeetCode 772 - Basic Calculator III
Techinpad: [LeetCode] Basic Calculator II
http://shibaili.blogspot.com/2015/06/day-113-basic-calculator-ii.html

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.

X. https://leetcode.com/problems/basic-calculator-ii/discuss/62996/Java-straight-forward-iteration-Solution-with-comments-No-Stack-O(N)-and-O(1)

public int calculate(String s) {
    if (s == null) return 0;
    s = s.trim().replaceAll(" +", "");
    int length = s.length();
    
    int res = 0;
    long preVal = 0; // initial preVal is 0
    char sign = '+'; // initial sign is +
    int i = 0;
    while (i < length) {
        long curVal = 0;
        while (i < length && (int)s.charAt(i) <= 57 && (int)s.charAt(i) >= 48) { // int
            curVal = curVal*10 + (s.charAt(i) - '0');
            i++;
        }
        if (sign == '+') {
            res += preVal;  // update res
            preVal = curVal;
        } else if (sign == '-') {
            res += preVal;  // update res
            preVal = -curVal;
        } else if (sign == '*') {
            preVal = preVal * curVal; // not update res, combine preVal & curVal and keep loop
        } else if (sign == '/') {
            preVal = preVal / curVal; // not update res, combine preVal & curVal and keep loop
        }
        if (i < length) { // getting new sign
            sign = s.charAt(i);
            i++;
        }
    }
    res += preVal;
    return res;
}

https://www.cnblogs.com/grandyang/p/4601208.html

    int calculate(string s) {
        long res = 0, curRes = 0, num = 0, n = s.size();
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            } 
        }
        return res;
    }

X.  https://www.jianshu.com/p/a69e8722c493

关键在于怎么处理乘法和除法，如果是乘法或者除法，我们需要用前面的数和当前的数做运算。因此此处可以用栈来记录前面的数字，用一个符号变量记录前一个符号，当遍历到一个新数字时，判断一下前面的符号是什么，如果是乘除，就和前面的数字运算，如果是+，就向栈中push这个数字，如果是-，就push这个数字的负数。
遍历到结尾，把最后一个数字入栈，此时栈中存放的都是要进行加法运算的数字。

https://leetcode.com/problems/basic-calculator-ii/discuss/63003/Share-my-java-solution
http://rainykat.blogspot.com/2017/04/leetcode-227-basic-calculator-ii-stack.html
思路： - use stack to store number after operation. initialize sign as '+'
           - calculating current val = val * 10 + char 
           - when meet next sign, perform operation of last sign on current number(+,-*,/)
           - finally sum up number in stack
eg: 2+33*2
            (here) sign = +, val = 33, then sign = *

public int calculate(String s) {
    int len;
    if(s==null || (len = s.length())==0) return 0;
    Stack<Integer> stack = new Stack<Integer>();
    int num = 0;
    char sign = '+';
    for(int i=0;i<len;i++){
        if(Character.isDigit(s.charAt(i))){
            num = num*10+s.charAt(i)-'0';
        }
        if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1){
            if(sign=='-'){
                stack.push(-num);
            }
            if(sign=='+'){
                stack.push(num);
            }
            if(sign=='*'){
                stack.push(stack.pop()*num);
            }
            if(sign=='/'){
                stack.push(stack.pop()/num);
            }
            sign = s.charAt(i);
            num = 0;
        }
    }

    int re = 0;
    for(int i:stack){
        re += i;
    }
    return re;
}

http://www.cnblogs.com/airwindow/p/4824721.html

Unlike the Calculator 1, this quesion is acutally much easier!!! You should do through a very tricky method.
To understand this problem, we should firstly understand the puzzle around this problem.
for equation like "22 - 31 * 52 + 22"
when we reach 31, we do not know whether to use it with 22, thus "22 - 31" or keep it for late usage.
In this situation, we apparenlty should not use it with 22 as "22 - 31", but use it with 52 as "31 * 52".

But we really could not know such information, until we reach "*" and get "52". Can we delay such calculation?
Yes!!!!
Why not decide the usage of 31 until we reach "+" after 52, when we have already know "*" and "52". 
We can do it!!!!

Suppose when reach a sign character "+ - * /", we have already know the number and the sign right before the number. 
(sign) num
---------------------------------------------------------------------------------------------------------
if (sign == '+')
    stack.push(num);

if (sign == '-')
    stack.push(-1 * num);

if (sign == '*')
    stack.push(stack.pop() * num);
if (sign == '/')
    stack.push(stack.pop() / num);

iff the sign is '*' or '/', we combine the preivous two numbers together. " (-31) * 52" as single number. (Just like we do the calculation manually. Right!!!)

----------------------------------------------------------------------------------------------------------
Skills:
1. how to get the num?
char c = s.charAt(i);
if (Character.isDigit(c)) 
    num = num*10 + (c - '0');
Note: Character.isDigit(c) is very elegant!

2. how to tackle the last num?
if (i == s.length() - 1) {
...
}

3. how to get the number before the current num.
stack.pop()

   public int calculate(String s) {
        if (s == null || s.length() == 0)
            return 0;
        Stack<Integer> stack = new Stack<Integer> ();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) 
                num = num*10 + (c - '0');
            if ((c != ' ' && !Character.isDigit(c)) || i == s.length() - 1) {
                if (sign == '+')
                    stack.push(num);
                if (sign == '-')
                    stack.push(-1 * num);
                if (sign == '*')
                    stack.push(stack.pop() * num);
                if (sign == '/')
                    stack.push(stack.pop() / num);
                sign = c;
                num = 0;
            }
        }
        int ret = 0;
        for (int i : stack) {
            ret += i;
        }
        return ret;
    }

http://www.cnblogs.com/grandyang/p/4601208.html
这道题是之前那道Basic Calculator 基本计算器的拓展，不同之处在于那道题的计算符号只有加和减，而这题加上了乘除，那么就牵扯到了运算优先级的问题，好在这道题去掉了括号，还适当的降低了难度，估计再出一道的话就该加上括号了。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了

http://yuanhsh.iteye.com/blog/2230551

1. public int calculate(String s) {  
2.     String[] arr = s.split("[\\+\\-\\*\\/]");  //
3.     String[] ops = s.split("\\d+");  //
4.     int n = arr.length;  
5.     int[] nums = new int[n];  
6.     for(int i=0; i<n; i++) {  
7.         nums[i] = Integer.parseInt(arr[i].trim());  
8.     }  
9.     for(int i=1; i<n; i++) {  
10.         char op = ops[i].trim().charAt(0);  
11.         if(op == '-') {  
12.             nums[i] = -nums[i];  
13.         } else if(op == '*') {  
14.             nums[i] = nums[i-1]*nums[i];  
15.             nums[i-1] = 0;  
16.         } else if(op == '/') {  
17.             nums[i] = nums[i-1]/nums[i];  
18.             nums[i-1] = 0;  
19.         }  
20.     }  
21.     int sum = 0;  
22.     for(int num:nums) sum += num;  
23.     return sum;  
24. }  

http://yuanhsh.iteye.com/blog/2194524
look ahead,COME_BACK, 如果加入括号呢？
    long long lookAhead(string &s, int &i) {
        long long num = 0;
        while (i < s.length()) {
            if (s[i] == ' ') {
                i++;
            }else if (isdigit(s[i])) {
                num = 10 * num + s[i] - '0';
                i++;
            }else
                break;
        }
       
        i--;
        return num;
    }

    int calculate(string s) {
        long long num = 0, rt = 0;
        long long sign = 1;
       
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = lookAhead(s,i);
            }else if (s[i] == '+') {
                rt += sign * num;
                sign = 1;
                num = 0;
            }else if (s[i] == '-') {
                rt += sign * num;
                sign = -1;
                num = 0;
            }else if (s[i] == '*') {
                i++;
                num *= lookAhead(s,i);
            }else if (s[i] == '/') {
                i++;
                num /= lookAhead(s,i);
            }
        }
       
        if (num > 0) return rt + sign * num;
        return rt;
    }

1.     int calculate(string s) {  
2.         vector<int> numbers;  
3.         vector<char> operators;  
4.         int i = 0;  
5.         while(i<s.length())  
6.         {  
7.             char e = s[i++];  
8.             if(e == ' ') continue;  
9.               
10.             if(isdigit(e))  
11.             {  
12.                 int j = i;  
13.                 while(j < s.length() && isdigit(s[j]) ) j++;  
14.                 int num = stoi(s.substr(i-1, j-i+1));  
15.                 i = j;  
16.                 if(!operators.empty() &&   
17.                     (operators.back() == '*'   
18.                     || operators.back() == '/')  
19.                   )  
20.                 {  
21.                     char op = operators.back();  
22.                     operators.pop_back();  
23.                     if(op == '*') numbers.back() *= num;  
24.                     else numbers.back() /= num;  
25.                 }  
26.                 else numbers.push_back(num);  
27.                   
28.             }  
29.             else operators.push_back(e);  
30.         }  
31.           
32.         if(numbers.empty()) return 0;  
33.         int a = numbers[0];  
34.         int opIndex = 0;  
35.         for(int i = 1;i<numbers.size();i++)  
36.         {  
37.             char op = operators[opIndex++];  
38.             if(op == '+') a += numbers[i];  
39.             else a -= numbers[i];  
40.         }  
41.         return a;  
42.     } 

Calculator: Given an arithmetic equation consisting of positive integers,+,-,* and/ (no parentheses),

compute t he result.

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2016.%20Moderate/Q16_26_Calculator

/* Return priority of operator. Mapped so that:

 *     addition == subtraction < multiplication == division. */

public static int priorityOfOperator(Operator op) {

  switch (op) {

  case ADD: return 1;

  case SUBTRACT: return 1;

  case MULTIPLY: return 2;

  case DIVIDE: return 2;

  case BLANK: return 0;

  }

  return 0;

}

/* Collapse top until priority(futureTop) > priority(top). 

 * Collapsing means to pop the top 2 numbers and apply the 

 * operator popped from the top of the operator stack, and then

 * push that onto the numbers stack.*/

public static void collapseTop(Operator futureTop, Stack<Double> numberStack, Stack<Operator> operatorStack) {

  while (operatorStack.size() >= 1 && numberStack.size() >= 2) {

    if (priorityOfOperator(futureTop) <= priorityOfOperator(operatorStack.peek())) {

      double second = numberStack.pop();

      double first = numberStack.pop();

      Operator op = operatorStack.pop();

      double collapsed = applyOp(first, op, second);

      numberStack.push(collapsed);

    } else {

      break;

    }

  }

}

public static double compute(String sequence) {

  Stack<Double> numberStack = new Stack<Double>();

  Stack<Operator> operatorStack = new Stack<Operator>();

  

  for (int i = 0; i < sequence.length(); i++) {

    try

    {

      /* Get number and push. */

      int value = parseNextNumber(sequence, i);

      numberStack.push((double) value);

      

      /* Move to the operator. */

      i += Integer.toString(value).length();

      if (i >= sequence.length()) {

        break;

      }

      

      /* Get operator, collapse top as needed, push operator. */

      Operator op = parseNextOperator(sequence, i);

      collapseTop(op, numberStack, operatorStack);

      operatorStack.push(op);

    } catch (NumberFormatException ex) {

      return Integer.MIN_VALUE;

    }

  }

  

  /* Do final collapse. */

  collapseTop(Operator.BLANK, numberStack, operatorStack);

  if (numberStack.size() == 1 && operatorStack.size() == 0) {

    return numberStack.pop();

  }

  return 0;

}

/* Compute the result of the arithmetic sequence. This works by reading left to

 * right and applying each term to a result. When we see a mu ltiplication or

 * division, we instead apply this sequence to a temporary variable. */

double compute(String sequence) {

        Arraylist<Term> terms = Term.parseTermSequence(sequence);

        if (terms == null) return Integer.MIN_VALUE;

        double result = 0;

        Term processing = null;

        for (int i= 0; i < terms.size(); i++) {

                Term current= terms.get(i);

                Term next= i + 1 < terms.size() ? terms.get(i + 1) : null;

                /* Apply the current term to "processing". */

                processing= collapseTerm(processing, current);

                /* If next term is + or -, then this cluster is done and we should apply

                 * "processing" to "result". */

                if (next== null || next.getOperator() == Operator.ADD

                    || next.getOperator() == Operator.SUBTRACT) {

                        result= applyOp(result, processing.getOperator(), processing.getNumber());

                        processing= null;

                }

        }

        return result;

}

/* Collapse two terms together using the operator in secondary and the numbers

 * from each. */

Term collapseTerm(Term primary, Term secondary) {

        if (primary== null) return secondary;

        if (secondary== null) return primary;

        double value= applyOp(primary.getNumber(), secondary.getOperator(),

                              secondary.getNumber());

        primary.setNumber(value);

        return primary;

}

double applyOp(double left, Operator op, double right) {

        if (op== Operator.ADD) return left+ right;

        else if (op Operator.SUBTRACT) return left - right;

        else if (op== Operator.MULTIPLY) return left * right;

        else if (op== Operator.DIVIDE) return left/ right;

        else return right;

}

public class Term {

public enum Operator {

        ADD, SUBTRACT, MULTIPLY, DIVIDE, BLANK

}

private double value;

private Operator operator= Operator.BLANK;

public Term(double v, Operator op) {

        value= v;

        operator= op;

}

public double getNumber() {

        return value;

}

public Operator getOperator() {

        return operator;

}

public void setNumber(double v) {

        value= v;

}

/* Parses arithmetic sequence into a list of Terms. For example, 3-5*6 becomes

 * something like: [{BLANK,3}, {SUBTRACT, 5}, {MULTIPLY, 6}}.

 * If improperly formatted, returns null. */

public static ArrayList<Term> parseTermSequence(String sequence) {

        ArrayList<Term> terms = new ArrayList<Term>();

        int offset = 0;

        while (offset < sequence.length()) {

                Operator op = Operator.BLANK;

                if (offset > 0) {

                        op = parseOperator(sequence.charAt(offset));

                        if (op == Operator.BLANK) {

                                return null;

                        }

                        offset++;

                }

                try {

                        int value = parseNextNumber(sequence, offset);

                        offset += Integer.toString(value).length();

                        Term term = new Term(value, op);

                        terms.add(term);

                } catch (NumberFormatException ex) {

                        return null;

                }

        }

        return terms;

}

public static Operator parseOperator(char op) {

        switch(op) {

        case '+': return Operator.ADD;

        case '-': return Operator.SUBTRACT;

        case '*': return Operator.MULTIPLY;

        case '/': return Operator.DIVIDE;

        }

        return Operator.BLANK;

}

public static int parseNextNumber(String sequence, int offset) {

        StringBuilder sb = new StringBuilder();

        while (offset < sequence.length() && Character.isDigit(sequence.charAt(offset))) {

                sb.append(sequence.charAt(offset));

                offset++;

        }

        return Integer.parseInt(sb.toString());

}

}

第二道有点像蠡口尔尔其，不过只有+和*和数字，不考虑其他的，我用的stack的方法做，问时间空间复杂度，然后follow up问能不能把空间复杂度降到O(1)

原来的想法的遇到 * 就算，遇到 + 就压到stack里
然后改成，遇到+或者末尾，就把当前的数字加到sum上去，如果是*当前的数字先设成1，然后不断乘，直到遇到+或者末尾，再加到总和上，不断循环