Share my java solution

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

}

• Really clearly!

• 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)``````

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

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

• This post is deleted!

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

• 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.

• Hey bro no parenthesis is allowed..

• 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

• This post is deleted!

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

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

• 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 .

• This post is deleted!

• why so many people vote down this solution?

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

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

• 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(" ", ""));
}
``````

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

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