224. Basic Calculator.md

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;
    }
}

二刷

1. 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;
    }
}

Third Time

• Method 1: Recursion 99.21% Solved by myself, no reference

   class Solution {
       private int index = 0;
       private char[] arr;
       public int calculate(String s) {
           arr = s.toCharArray();
           return parse();
       }
       private int parse(){
           int sum = 0;
           int sign = 1;
           while(index < arr.length && arr[index] != ')'){
               char c = arr[index];
               if(c == '('){
                   index++;
                   sum += sign * parse();
               }else if(Character.isDigit(c)){
                   int temp = arr[index] - '0';
                   index++;
                   while(index < arr.length && Character.isDigit(arr[index])){
                       temp = temp * 10 + arr[index] - '0';
                       index++;
                   }
                   sum += sign * temp;
                   index--;
               }else if(c == '+'){
                   sign = 1;
               }else if(c == '-'){
                   sign = -1;
               }else if(c == ')'){
                   index++;
                   return sum;
               }
               index++;
           }
           return sum;
       }
   }