224. Basic Calculator

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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Thinking:

Method 1：
- 通过while读取出所有的数字。
- 维护一个sign变量。维护一个res变量，用于存储当前段（在同一个括号内）的值。
- 当遇到+/-时，更新sign变量。
- 遇到(时，将当前的res和sign入栈。
- 当遇到)时，读出sign和括号外部的res，进行计算。

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

二刷

Refer to previous answer.

class Solution {
 public int calculate(String s) {
     char[] arr = s.toCharArray();
     Stack<Integer> stack = new Stack<>();
     int sign = 1;
     int result = 0;
     int len = arr.length;
     for(int i = 0; i < arr.length; 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');
             result += num * sign;
         }else if(c == '+'){
             sign = 1;
         }else if(c == '-'){
             sign = -1;
         }else if(c == '('){
             stack.push(result);
             stack.push(sign);
             result = 0;
             sign = 1;
         }else if(c == ')'){
             sign = stack.pop();
             result = stack.pop() + sign * result;
         }
     }
     return result;
 }
}