224. Basic Calculator

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 .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Solution,

Because the existence of parentheses, a stack is necessary to keep track any calculated sum and the operator sign right before it. Eg 2+(3+4-(5+6)) the stack would be 2, 1 when the iterator hits the first '(', the stack becomes 2,1,7,-1 when it hits the second '(', calculate sum by sum* stack.pop()+stack.pop() when iterator hits closing parentheses. We also keep track of current sum, and operator sign with two variables. So if there is no parentheses, we just calculate the sum by sum+num*sign. Obviously, if current char is '+', we update sign to positive 1 while if current char is '-' update sign to negative 1.Any open '(' means a new start and we reset sum and sign to default which are 0 and 1. 

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