JAVA-----------Easy Version To Understand!!!!!


  • 173
    H
    public static int calculate(String s) {
    	int len = s.length(), sign = 1, result = 0;
    	Stack<Integer> stack = new Stack<Integer>();
    	for (int i = 0; i < len; i++) {
    		if (Character.isDigit(s.charAt(i))) {
    			int sum = s.charAt(i) - '0';
    			while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
    				sum = sum * 10 + s.charAt(i + 1) - '0';
    				i++;
    			}
    			result += sum * sign;
    		} else if (s.charAt(i) == '+')
    			sign = 1;
    		else if (s.charAt(i) == '-')
    			sign = -1;
    		else if (s.charAt(i) == '(') {
    			stack.push(result);
    			stack.push(sign);
    			result = 0;
    			sign = 1;
    		} else if (s.charAt(i) == ')') {
    			result = result * stack.pop() + stack.pop();
    		}
    
    	}
    	return result;
    }

  • 0
    A

    wow, this is the best answer to understand,


  • 0
    H

    thanks !! please give me one vote!!


  • -2
    9

  • -2

  • 0
    H

    wow~brilliant!!


  • 0
    W

    The best answer!


  • 0
    V

    Elegant code and solution. Changing stack to array based stack shoots up the running time. Below is the array based stack version of your code.

        public int calculate(String s) {
            if(s == null || s.isEmpty()) return 0;
            int result = 0, sign = 1, len = s.length(),top = 0;
            int[] stack = new int[len]; // custom stack based on array
            for(int i = 0 ; i < len ; i++){
                char c = s.charAt(i);
                if(c >= '0' && c <= '9' ){
                    int num = c - '0';
                    while(i + 1 < len && s.charAt(i+1)  >= '0' && s.charAt(i+1) <= '9')
                        num = num*10 + (s.charAt(i++ + 1) - '0');
                    result += num * sign;
                }else if(c == '+' || c == '-'){
                    sign = c == '+' ? 1 : -1 ;
                }else if( c == '('){
                    stack[top++] = result; // push 
                    stack[top++] = sign; // push
                    result = 0;
                    sign = 1;
                }else if(c == ')'){
                    result = result * stack[--top] + stack[--top]; // first pop is for sign which says negative or positive.
                }
            }
            return result;
        }
    

  • 2

    Amazing solution! Very easy to understand. Here is the version that always keeps the most recent sum at the top of stack without variable result.

        // Inspired by solution from leetcode discuss
        public int calculate(String s) {
            Stack<Integer> stack = new Stack<>();
            stack.push(0);                          // Always keep most recent sum at top
            for (int i = 0, sign = 1; i < s.length(); i++) {
                if (Character.isDigit(s.charAt(i))) {
                    int num = s.charAt(i) - '0';    // Be aware of outer loop boundary and i++
                    for (; i < s.length() - 1 && Character.isDigit(s.charAt(i + 1)); i++) {
                        num = num * 10 + (s.charAt(i + 1) - '0');
                    }
                    stack.push(stack.pop() + sign * num);
                } else if (s.charAt(i) == '+') {
                    sign = 1;
                } else if (s.charAt(i) == '-') {
                    sign = -1;
                } else if (s.charAt(i) == '(') {
                    stack.push(sign);
                    stack.push(0);
                    sign = 1;
                } else if (s.charAt(i) == ')') {    // Update last sum = current sum * sign
                    stack.push(stack.pop() * stack.pop() + stack.pop());
                } /* else whitespace*/
            }
            return stack.pop();
        }
    

  • 0
    S
    This post is deleted!

  • 0
    Y

    very simple and clarified, cool!


  • 0
    H

    Very Easy to understand solution!! Thanks!


  • 0
    N

    this is the best solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.