227. Basic Calculator II

227. Basic Calculator II

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.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Thinking:

• Method 1：使用栈，当遇到*或/时，直接计算值再入栈。

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

二刷

1. Same idea as the first shot.
2. I used a placeholder to save the previous operation
   • +: put the result into stack directly.
   • -: put negative value into the stack.
   • • & /: do the operation first and save the result into stack.

       class Solution {
        public int calculate(String s) {
       int len = s.length();
       char[] arr = s.toCharArray();
       Stack<Integer> stack = new Stack<>();
       char opt = ' ';
       for(int i = 0; i < len; i++){
           char c = arr[i];
           if(Character.isDigit(c)){
               int num = c - '0';
               while(i + 1 < len && Character.isDigit(arr[i + 1])){
                   num = num * 10 + arr[++i] - '0';
               }
               if(opt == '*'){
                   int pre = stack.pop();
                   stack.push(pre * num);
               }else if(opt == '/'){
                   int pre = stack.pop();
                   stack.push(pre / num);
               }else if(opt == '-'){
                   stack.push(-1 * num);
               }else{
                   stack.push(num);
               }
           }else if(c == '+' ||c == '-' ||c == '*' || c == '/'){
               opt = c;
           }
       }
       int result = 0;
       for(Integer i : stack)
           result += i;
       return result;
        }
       }