224. Basic Calculator & 227. Basic Calculator

摘要：题目链接，就是感觉条件有点多简单点的写法，把直接用存在里面，就存成，存成题目链接这题就是碰到在加减后面怎么处理的问题。用一个来表示之前的，所以碰到现在是乘的时候就，除类似。

题目链接：https://leetcode.com/problems...

stack，就是感觉条件有点多

public class Solution {
    public int calculate(String s) {
        Stack nums = new Stack();
        Stack signs = new Stack();
        int prev = 0,  cur = 0;
        char sign = "#";
        int i = 0;
        /* prev: number before sign, cur: number after sign, sign
         * push: meet "(", put prev, sign = "#"
         * pop: meet ")" if not empty
         * number: do caculate if sign != "#"
         */
        // start of number or sign or "(" or ")"
        while(i < s.length()) {
            char c = s.charAt(i);
            // number
            if(Character.isDigit(c)) {
                while(i < s.length() && Character.isDigit(s.charAt(i))) cur = cur * 10 + (s.charAt(i++) - "0");
                i--;
                if(sign == "+")  prev += cur;
                else if(sign == "-")  prev -= cur;
                else prev = cur;
                cur = 0;
            }
            else if(c == "(") {
                // in case of "(1 + 2)"
                if(sign != "#") {
                    nums.push(prev);
                    signs.push(sign);
                    sign = "#";
                    prev = 0;
                }
            }
            else if(c == ")") {
                if(!nums.isEmpty()) {
                    int temp = nums.pop();
                    sign = signs.pop();
                    if(sign == "+") prev += temp;
                    else prev = temp - prev;
                    sign = "#";
                }
            }
            else if(c == "+" || c == "-") sign = c;
            // update
            i++;
        }
        
        return prev;
    }
}

简单点的写法，把sign直接用int存在stack里面，"+"就存成1， "-"存成-1

public class Solution {
    public int calculate(String s) {
        Stack nums = new Stack();
        Stack signs = new Stack();
        int prev = 0,  cur = 0;
        int sign = 1;
        int i = 0;
        /* prev: number before sign, cur: number after sign, sign
         * push: meet "(", put prev
         * pop: meet ")" if not empty
         * number: do caculate 
         */
        // start of number or sign or "(" or ")"
        while(i < s.length()) {
            char c = s.charAt(i);
            // number
            if(Character.isDigit(c)) {
                while(i < s.length() && Character.isDigit(s.charAt(i))) {
                    cur = cur * 10 + (s.charAt(i++) - "0");
                }
                i--;
                prev = prev + sign*cur;
                cur = 0;
            }
            else if(c == "(") {
                nums.push(prev);
                signs.push(sign);
                sign = 1;
                prev = 0;
            }
            else if(c == ")") {
                prev = nums.pop() + signs.pop() * prev;
            }
            else if(c == "+") sign = 1;
            else if(c == "-") sign = -1;
            // update
            i++;
        }
        
        return prev;
    }
}

题目链接：https://leetcode.com/problems...

这题就是碰到"*", "/"在加减后面怎么处理的问题。用一个prev来表示之前的number，所以碰到现在是乘的时候就：res = res - prev + prev * cur, prev = prev * cur，除类似。

public class Solution {
    public int calculate(String s) {
        int res = 0;
        int prev = 0;
        s = s.replaceAll("[^0-9^+-/*]", "");
        int i = 0, n = s.length();
        // first number
        while(i < n && Character.isDigit(s.charAt(i))) {
            prev = prev * 10 + (s.charAt(i++) - "0");
        }
        res = prev;
        // loop invariant: start from sign: -, +, *, /
        while(i < n) {
            char c = s.charAt(i++);
            int cur = 0;
            while(i < n && Character.isDigit(s.charAt(i))) {
                cur = cur * 10 + (s.charAt(i++) - "0");
            }
            if(c == "+") {
                res += cur;
                prev = cur;
            }
            else if(c == "-") {
                res -= cur;
                prev = -cur;
            }
            else if(c == "*") {
                res = res - prev + prev * cur;
                prev *= cur;
            }
            else if(c == "/") {
                res = res - prev + prev / cur;
                prev /= cur;
            }
        }
        return res;
    }
}