2015年11月3日星期二

Leetcode 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
Solution 1: Use stack
 public class Solution {  
   public int calculate(String s) {  
     Deque<Integer> stack=new LinkedList<>();  
     int n=s.length();  
     int res=0, sign=1;  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)<='9' && s.charAt(i)>='0') {  
         int j=i, num=0;  
         while (j<n && s.charAt(j)<='9' && s.charAt(j)>='0') num=num*10+s.charAt(j++)-'0';  
         res+=sign*num;  
         i=j-1;  
       }  
       else if (s.charAt(i)=='+') sign=1;  
       else if (s.charAt(i)=='-') sign=-1;  
       else if (s.charAt(i)=='(') {  
         stack.push(res);  
         stack.push(sign);  
         res=0;  
         sign=1;  
       }  
       else if (s.charAt(i)==')') {  
         sign=stack.pop();  
         int pre=stack.pop();  
         res=pre+sign*res;  
       }  
     }  
     return res;  
   }  
 }  

没有评论:

发表评论