Share my java solution


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

    }


  • 0
    M

    Really clearly!


  • -5
    F

    Excellent!
    Rewrite with python:

    def calculate(s):
        l=list(s)
        if len(l) == 0: return 0;
        num=0
        sign='+'
        stack = []
        for idx,i in enumerate(l):
        	if i.isdigit():
        		num=num*10+int(i)
        	# when the signs occurs,time to calculate your number
        	if (i in ('+','-','*','/')) or idx==len(l)-1:
        		if sign=='+':
        			stack.append(num)
        		if sign=='*':
        			stack.append(int(stack.pop()) * num)
        		if sign=='-':
        			stack.append(-num)
        		if sign=='/':
       			    top = int(stack.pop())
       			    if top >= 0:
       			    	stack.append( top / num)
       			    else:
       			        stack.append(-( abs(top) / num  ))
        		sign = i 
        		num=0
        return sum(stack)

  • 0
    D

    That's cool. But why we don't need to check Integer.MAX_VALUE or Integer.MIN_VALUE for each case?


  • -5
    C

    Very clever method, your solution inspired mine: https://leetcode.com/discuss/68953/10-lines-python-solution


  • -20
    J
    This post is deleted!

  • -1
    J

    This solution may be wrong. I get an exception for the following test case: "2*6-(23+7)/(1+2)"


  • 3
    Y

    I dont understand this solution. the line:

    "if(sign=='*'){
    stack.push(stack.pop()*num);
    }"

    how can you process "*" without known the next number?

    say, a times b, you did the multiplication when you see a "*", how can you do that? you have not seen "b" yet? can someone teach me?I'm lost.


  • 3

    Hey bro no parenthesis is allowed..


  • 0

    when you see '' what you are going to do is push 'a' into stack and assign '' to variable sign.
    Then when you see b, you pop a back and do ab. So you can get the result ab


  • 0
    J
    This post is deleted!

  • 0
    L

    Parentheses are not supposed to be included. Read the question.


  • 0
    X

    @javadev because there is no "(" and ")" in this case


  • 0
    S

    at the beginning the sign is + , so when you see a*b, you first push in a, then set the sign to , then compute ab .


  • 0
    C
    This post is deleted!

  • 0
    Y

    why so many people vote down this solution?


  • 0
    W

    shouldn't we change
    int num = 0
    to
    long num = 0
    in case overflow?


  • 2

    This solution is awesome, and you could improve the efficiency by remove the last iteration of stack. Here is my code:

    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0, res = 0;
        char sign = '+';
        char[] sArray = s.toCharArray();
        for(int i=0; i<sArray.length; i++) {
            char c = sArray[i];
            if(c >= '0' && c <= '9') {
                if(10 * num + (c - '0') > Integer.MAX_VALUE) num = Integer.MAX_VALUE;
                else num = 10 * num + (c - '0');
            }
            
            if(c == '+' || c == '-' || c == '*' || c == '/' || i == sArray.length-1) {
                if(sign == '+' || sign == '-') {
                    int tmp = sign == '+' ? num : -num;
                    stack.push(tmp);
                    res += tmp;
                } else {
                    res -= stack.peek();
                    int tmp = sign == '*' ? stack.pop() * num : stack.pop() / num;
                    stack.push(tmp);
                    res += tmp;
                }
                sign = c;
                num = 0;
            }
        }
        return res;
    }
    

  • 7

    Very clear solution! Agree that the final iteration of stack could be got rid of. Now the code is even more concise. Thanks for your sharing!

        public int calculate(String s) {
            Stack<Integer> stack = new Stack<>();
            int result = 0;
            for (int i = 0, num = 0, op = '+'; i < s.length(); i++) {   // op is last operator
                char c = s.charAt(i);
                if (Character.isDigit(c))
                    num = num * 10 + (c - '0');
                if ("+-*/".indexOf(c) >= 0 || i == s.length() - 1) {    // must be 'if' or i=len-1 won't reach here
                    if ("*/".indexOf(op) >= 0)                          // subtract top before mul/div
                        result -= stack.peek();
                    switch (op) {
                        case '+': stack.push(num); break;
                        case '-': stack.push(-num); break;
                        case '*': stack.push(stack.pop() * num); break; // only non-negative int, impossible '2*-1'
                        case '/': stack.push(stack.pop() / num); break;
                    }
                    num = 0;
                    op = c;
                    result += stack.peek();
                } /* else whitespace */
            }
            return result;
        }
    

    ps: The idea is to perform multiplication and division first (they are on the lower level in the expression tree), then subtract and addition. So basically this is the bottom-up apporach to evaluate the implicit expression tree. I think It's essentially the same as the top down version below.

        public int calculate(String s) {
            for (int i = 0; i < s.length(); i++)
                if (s.charAt(i) == '+') 
                    return calculate(s.substring(0, i)) + calculate(s.substring(i + 1));
    
            for (int i = 0; i < s.length(); i++) // '-' must perform with two closest numbers, eg.2+3 - 4+1=1 not 0
                if (s.charAt(i) == '-')
                    return calculate(s.substring(0, i)) - calculate(s.substring(i + 1));
            
            for (int i = s.length() - 1; i >= 0; i--) { // must perform in order
                if (s.charAt(i) == '*')
                    return calculate(s.substring(0, i)) * calculate(s.substring(i + 1));
                if (s.charAt(i) == '/')
                    return calculate(s.substring(0, i)) / calculate(s.substring(i + 1));
            }
            return Integer.parseInt(s.replace(" ", ""));
        }
    

  • 1
    2

    if(sign=='-'){ stack.push(-num); }
    This line is great! So we don't need to keep another stack of '+'s and '-'s.


Log in to reply
 

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